Testing membership in matroid polyhedra

Given a matroid M on E and a nonnegative real vector x=(x_j:j∈E), a fundamental problem is to determine whether x is in the convex hull P of (incidence vectors of) independent sets of M. An algorithm is described for solving this problem for which the amount of computation is bounded by a polynomial in |E|, independently of x, allowing as steps tests of independence in M and additions, subtractions, and comparisons of numbers. In case x ∈ P, the algorithm finds an explicit representation for x which has additional nice properties; in case x ? P it finds a most-violated inequality of the system defining P. The same technique is applied to the problem of finding a maximum component-sum vector in the intersection of two matroid polyhedra and a box.     

Shuffle of parenthesis systems and baxter permutations

A formula for the number alternating Baxter permutations is given. The proof of this formula is given by constructing bijection between permutations, trees, and words. This gives also a combinatorial proof of a formula appearing in the enumerative theory of planar maps.     

Permutations, parenthesis words, and Schröder numbers

A different proof for the following result due to West is given: the Schröder number s[inn−1] equals the number of permutations on [1,2,] …, nþat avoid the pattern (3,1,4,2) and its dual (2,4,1,3).     

Neural languages

In order to provide the theoretical framework necessary to study the neural mechanisms underlying languages, we present here a mathematical formalization of some neural behaviors. In such a context: (i) the neuron is defined as a coupling of automata, dealing with the transduction and codifying processes; (ii) the coupling between neurons is measured by a membership relation defined as the ratio between the transmitted and the system entropies; (iii) the attention given to the messages arriving at the system is considered as the difference between the couplings of the excitatory and inhibitory pools of neurons; (iv) the graphs in the neural systems are described by means of these couplings and, finally (v) the semantic productions are described by the fuzzy formal languages accepted by the automata formalized on these graphs. In such a way, both the verbal and neural semantics can now be correlated and experimentally investigated.     

Conjugacy languages in groups

We study the regularity of several languages derived from conjugacy classes in a finitely generated group G for a variety of examples including word hyperbolic, virtually abelian, Artin, and Garside groups. We also determine the rationality of the growth series of the shortlex conjugacy language in virtually cyclic groups, proving one direction of a conjecture of Rivin.     

Part-compilation in high-level languages

Many programming languages include the ability to divide large programs into smaller segments, which are compiled separately. When a small modification is made to a large program, then the affected segment only has to be re-compiled.This paper discusses how high-level languages like Algol 68, Algol W or Simula 67 can incorporate part-compilation in a usable, secure and efficient way.     

Restorations of punctured languages and similarity of languages

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ ‐similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non‐slender linear languages. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bargaining and membership

In coalitional games in which the players are partitioned into groups, we study the incentives of the members of a group to leave it and become singletons. In this context, we model a non-cooperative mechanism in which each player has to decide whether to stay in her group or to exit and act as a singleton. We show that players, acting myopically, always reach a Nash equilibrium.     

System function languages

In this paper we define the concept of a system function language which is a language generated by a system function. We identify system function languages with recursively enumerable sets which are non-simple and co-infinite. We then define restricted system function languages and identify them with recursive sets which are co-infinite. Finally we state and prove some independence and dependence relationships between system function languages and some of the more well-known decision problems. MSC: 03D05, 03D20, 03D25.     

Multiple inheritance in Simula-like languages

This paper examines the subclass mechanism offered in the Simula language, and discusses how the flexibility of this mechanism would be enhanced if more than one prefix were allowed for classes (multiple inheritance). A strategy is presented for implementing this with efficiency comparable to that of current Simula.     

On-line user languages

The principal differences between on-line and off-line user languages are discussed in some detail. The characteristic features of the OPL programming language are mentioned together with experiences of Project MAC, pointing at increased efficiency in the use of computers.Work reported herein was supported by Project MAC, and M. I. T. research program sponsored by the Advanced Research Projects Agency, Department of Defense, under Office of Naval Research contract NONR-4102(01). Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Relatively f-disjunctive languages

Communicated by Boris M. Schein     

Machine dependent programming in common languages

It is suggested that we should distinguish between common programming languages and common solutions to specific problems. A solution may depend on specific machine characteristics even though it is expressed in a common language. It is further suggested that in future common programming languages this should be admitted openly by allowing the programmer to get access to the machine characteristics at hand through Environment Enquiries which are part of the language. Some specific examples of Environment Enquiries are given.An earlier version of this paper was published in ALGOL BULLETIN no. 18, October 1964.     

About membership functions estimation

A logical approach to fuzzy sets method originated by Giles is developed. The infinitely many-valued logic t_ω is taken as basic. We accept, it is correct to use the strong conjunction by the logical analysis of the summation of fuzzy items. Under some broad conditions it is proved. that the sum of many fuzzy variables is a variable whose membership function is approximately equal to $\text{?(x) =}\text{max}\text{{1 ?}\text{1}\text{2}\text{c(x ? α)}{}^2\text{, 0}}$, where a and c are some constant parameters. A method of estimation of the unknown parameters is developed in a general case. The proposed fuzzy method coincides with the method of maximum likelihood if used in problems of classical mathematical statistics.     

Automatic error correction in inflected languages

Systems for automatic detection and correction of spelling errors in natural language texts are considered. The development of such systems for both English and Russian (and for inflected languages in general, including all Slavic languages) is discussed. An approach associated with morphological analysis of the wordforms in the given text is described. The topics considered in the paper include the main methods of automatic spelling correction, levels of automation of the spelling error correction process, the effect of the type of computer used, the use of spelling error correctors in a stand-alone mode and in combination with word-processing software, and the maintenance of auxiliary dictionaries.Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 28, pp. 111–139, 1988.