Classes of regular and context-free languages over countably infinite alphabets

For a countably infinite alphabet Δ, the classes Reg(Δ) of regular languages and CFL(Δ) of context-free languages over Δ are defined by way of an encoding. All the languages contained in these classes are decidable, and these classes do have many properties in common with the class of regular languages Reg(Σ) and the class of context-free languages CFL(Σ), respectively, where Σ is a finite alphabet. In particular, each of these classes can be characterized in a semantical way by a certain type of automata over Δ. Finally, the classes Reg(Δ) and CFL (Δ) are compared to the classes of languages over Δ that are defined by Autebert, Beauquier, and Boasson.     

Automaticity of semigroups of regular languages

It is proved that there exist semigroups of regular languages not possessing automatic structure of a certain special form and also that semigroups of regular languages over a one-letter alphabet are automatic.     

On the word problem for syntactic monoids of piecewise testable languages

Piecewise testable languages are widely studied area in the theory of automata. We analyze the algebraic properties of these languages via their syntactic monoids. In this paper a normal form is presented for 2- and 3-piecewise testable languages and a log-asymptotic estimate is given for the number of words over these monoids.     

Disjunctive splittability of languages

Decompositions of languages over a finite alphabetX are investigated. Let T be a class of languages overX satisfying the following condition: (#) T contains at least one dense language, and every dense subset of an element in T is again in T. A language is said to be DT-splittable if it is a disjoint union of infinitely many discrete disjunctive languages in T which are locally finite of rank 1. It is shown that a language is DT-splittable if and only if it is a union of dense languages in T. The class P of all prefix codes satisfies the condition (#). DP-splittability of languages is investigated in detail. A language A is said to besemi-DT-splittable if A\F is DT-splittable for some finite languageF. Semi-DP-splittability is investigated. Semi-DP-splittability of catenations of languages is also studied.     

Growth of power-free languages: Numerical and asymptotic bounds

We consider power-free languages over finite alphabets. That is, the words which are powers with the exponent greater than a given constant cannot be factors of words in these languages. We give numerical bounds of the exponential growth rate for a wide range of such languages. These bounds are obtained using the algorithms proposed by the author. On the basis of these bounds we suggest the asymptotic behaviour of the growth rate as a function of the exponent and the size of the alphabet, and give some theorems about this behaviour.     

Regular Component Splittable Languages

Every infinite regular language contains a regular subset of the formuv+w for some words u, v, w, where v is not the empty word. The regularsubsets of the above form are called regular components. Some well-knowncontext-free languages, such as the Dyck language and the balanced language(over an alphabet X with |X| = 2), are decomposed as disjointunions of disjunctive languages. In this paper, we investigate thedecompositions of some of the regular languages and the context-freelanguages as disjoint unions of regular components. An infinite language iscalled regular component splittable if it can be expressed as a disjointunion of regular components and a finite set. We show that the Dycklanguage, the balanced language and some disjunctive context-free splittablelanguages are regular component splittable. We also present an example toshow that there is a disjunctive context-free language which is not regularcomponent splittable.     

Objective Bayesian probabilistic logic

This paper develops connections between objective Bayesian epistemology—which holds that the strengths of an agent's beliefs should be representable by probabilities, should be calibrated with evidence of empirical probability, and should otherwise be equivocal—and probabilistic logic. After introducing objective Bayesian epistemology over propositional languages, the formalism is extended to handle predicate languages. A rather general probabilistic logic is formulated and then given a natural semantics in terms of objective Bayesian epistemology. The machinery of objective Bayesian nets and objective credal nets is introduced and this machinery is applied to provide a calculus for probabilistic logic that meshes with the objective Bayesian semantics.     

Improved Alignment-Based Algorithm for Multilingual Text Compression

Multilingual text compression exploits the existence of the same text in several languages to compress the second and subsequent copies by reference to the first. This is done based on bilingual text alignment, a mapping of words and phrases in one text to their semantic equivalents in the translation. A new multilingual text compression scheme is suggested, which improves over an immediate generalization of bilingual algorithms. The idea is to store the necessary markup data within the source language text; the incurred compression loss due to this overhead is smaller than the savings in the compressed target language texts, for a large enough number of the latter. Experimental results are presented for a parallel corpus in six languages extracted from the EUR-Lex website of the European Union. These results show the superiority of the new algorithm as a function of the number of languages.     

On dos languages and dos mappings

Roughly speaking,DOS systems formalize the notion of generatively deterministic context free grammars. We explore the containment relationships among the class of languages generated byDOS systems and other subclasses of the class of context free languages. Leaving the axiom of aDOS system unspecified yields aDOS scheme, which defines a mapping from words to languages over a given alphabet. We explore the algebraic properties ofDOS mappings and obtain an algebraic characterization of a fundamental subclass of theDOS mappings generated byDOS schemes which are propagating (non erasing) and have no cycles of derivability among letters of the alphabet. We apply this characterization to show that the mapping equivalence problem for propagatingDOS schemes is decidable.     

Base-free formulas in the lattice-theoretic study of compacta

The languages of finitary and infinitary logic over the alphabet of bounded lattices have proven to be of considerable use in the study of compacta. Significant among the sentences of these languages are the ones that are base free, those whose truth is unchanged when we move among the lattice bases of a compactum. In this paper we define syntactically the expansive sentences, and show each of them to be base free. We also show that many well-known properties of compacta may be expressed using expansive sentences; and that any property so expressible is closed under inverse limits and co-existential images. As a byproduct, we conclude that co-existential images of pseudo-arcs are pseudo-arcs. This is of interest because the corresponding statement for confluent maps is still open, and co-existential maps are often??but not always??confluent.     

Equal matrix languages and Kleene closure

It is shown that the family of equal matrix languages (EML) which intersects the family of context-sensitive and context-free languages is not closed under Kleene closure, intersection and complementation. The family of bounded EML whose generative power lies between that of bounded context-sensitive languages and bounded context-free languages is shown to be a class of unambiguous languages. Operations that preserve unambiguity and certain decidability questions are discussed.     

On intermediate factorial languages

We prove that factorial languages defined over non-trivial finite alphabets under some natural conditions have intermediate complexity functions, i.e., the number of words in such a language grows faster than any polynomial but slower than any exponential function.     

Langages sur des alphabets infinis

This paper proposes three possible definitions of context-free languages over infinite alphabets. These are proved to be non-equivalent and, in fact, of increasing power. For each of them, the classical results about CFL's as well as the usual closure properties are looked at. This work will be followed by two forthcoming papers using these notions: one for defining Languages' Form (similar to Grammars Form), the other for beginning the study of limits of languages which plays an important role in the theory of formal languages.     

Prefix-primitivity-preserving homomorphisms

This paper aims to investigate homomorphisms which preserve p-primitive languages. A characterization of p-primitivity-preserving homomorphisms can be detected within finite steps. Also the set of square-freeness-preserving homomorphisms is shown to be a proper subfamily of the set of p-primitivity-preserving homomorphisms. For homomorphisms over an alphabet X with |X|=2, it is also shown that the set of p-primitivity-preserving homomorphisms is a proper subfamily of the set of primitivity-preserving homomorphisms. But it is conjectured to also hold for homomorphisms over an alphabet with more than two letters.     

Combinatorial properties of boundary NLC graph languages

Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs)which rewrite single nodes only and establish connections between the embedded graph and the neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels, languages of unlabeled graphs). Boundary NLC (BNLC) grammars are NLC grammars with the property that whenever - in a graph already generated - two nodes may be rewritten, then these nodes are not adjacent. The graph languages generated by this type of grammars are called BNLC languages.In this paper we investigate the behaviour of graph invariants within BNLC languages. First we demonstrate that there is a dependency between the chromatic number and the clique number of graphs in BNLC languages (while this is wellknown not to be true for arbitrary graph languages). Secondly, we introduce a new graph invariant, the so-called index of a graph which seems to be very suitable for describing the adjacency structure of a graph. Then we prove that every BNLC language is of bounded index (which is shown not to be true for arbitrary graph languages). Thus we exhibit properties (concerning graph invariants) of BNLC languages which are intrinsic to this class. We use them to demonstrate that certain graph languages are not BNLC languages.     

Comparing eye movements during mathematical word problem solving in Chinese and German

Language plays an important role in word problem solving. Accordingly, the language in which a word problem is presented could affect its solution process. In particular, East-Asian, non-alphabetic languages are assumed to provide specific benefits for mathematics compared to Indo-European, alphabetic languages. By analyzing students’ eye movements in a cross-linguistic comparative study, we analyzed word problem solving processes in Chinese and German. 72 German and 67 Taiwanese undergraduate students solved PISA word problems in their own language. Results showed differences in eye movements of students, between the two languages. Moreover, independent cluster analyses revealed three clusters of reading patterns based on eye movements in both languages. Corresponding reading patterns emerged in both languages that were similarly and significantly associated with performance and motivational-affective variables. They explained more variance among students in these variables than between the languages alone. Our analyses show that eye movements of students during reading differ between the two languages, but very similar reading patterns exist in both languages. This result supports the assumption that the language alone is not a sufficient explanation for differences in students’ mathematical achievement, but that reading patterns are more strongly related to performance.     

Finite turns and the regular closure of linear context-free languages

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time.     

Sur les automates qui reconnaissent une famille de langages

The main results about automatas and the languages they accept are easily extended to automatas which recognize a family of languages (L_i)_iεI of a free monoid, that is to automatas which recognize simultaneously all the languages L_i. This generalization enhances the notion of automata of type (p,r) introduced by S. Eilenberg [4]. In a similar way the notion of syntactic monoid of a family of languages extends the notion of syntactic monoid of a language. This extension is far from being trivial since we show that every finite monoid is the syntactic monoid of a recognizable partition of a free monoid, though this is false for the syntactic monoids of languages.      

From finitary to infinitary second‐order logic

A back and forth condition on interpretations for those second‐order languages without functional variables whose non‐logical vocabulary is finite and excludes functional constants is presented. It is shown that this condition is necessary and sufficient for the interpretations to be equivalent in the language. When applied to second‐order languages with an infinite non‐logical vocabulary, excluding functional constants, the back and forth condition is sufficient but not necessary. It is shown that there is a class of infinitary second‐order languages whose non‐logical vocabulary is infinite for which the back and forth condition is both necessary and sufficient. It is also shown that some applications of the back and forth construction for second‐order languages can be extended to the infinitary second‐order languages. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)