Notes on top-down languages

Properties of context-free languages and grammars permitting deterministic top-down recognition with bounded lookahead are discussed. In particular, it is shown that for eachk>1 there are such languages requiring a lookahead of at leastk characters.     

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.     

146号初等元胞自动机的演化语言的复杂性

Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent （under conjugation） elementary cellular automaton of rule 182.     

Table systems with unconditional transfer

The family of languages generated by context-free programmed grammars equals that generated by context-free grammars with graph-controlled tables under unconditional transfer.     

On context-free and Szilard languages

Szilard languages of context-free grammars are studied. Especially, classical pumping, generalized pumping, Sokolowski's criterion, and semilinearity are considered as possible distinguishing properties between context-free and Szilard languages.This work was supported by the Academy of Finland.     

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.     

On permutative grammars generating context-free languages

A grammar is said to be permutative if it has permutation productions of the formAB BA in addition to context-free productions. Szilard languages and label languages are studied as examples of languages generable by permutative grammars. Particularly, sufficient conditions for a permutative grammar to generate a context-free language are studied.This work was supported by the Academy of Finland.     

Language-theoretic complexity of disjunctive sequences

A sequence over an alphabet ∑ is called disjunctive if it contains all possible finite strings over ∑ as its substrings. Disjunctive sequences have been recently studied in various contexts. They abound in both category and measure senses. In this paper we measure the complexity of a sequence x by the complexity of the language P(x) consisting of all prefixes of x. The languages P(x) associated to disjunctive sequences can be arbitrarily complex. We show that for some disjunctive numbers x the language P(x) is context-sensitive, but no language P(x) associated to a disjunctive number can be context-free. We also show that computing a disjunctive number x by rationals corresponding to an infinite subset of P(x) does not decrease the complexity of the procedure, i.e. if x is disjunctive, then P(x) does not have an infinite context-free subset. This result reinforces, in a way, Chaitin's thesis (1969) according to which perfect sets, i.e. sets for which there is no way to compute infinitely many of its members essentially better (simpler/quicker) than computing the whole set, do exist. Finally we prove the existence of the following language-theoretic complexity gap: There is no x ε ∑^w such that P(x) is context-free but not regular. If S(x), the set of all finite substrings of a sequence x ε ∑^w, is slender, then the set of all prefixes of x is regular, that is P(x) is regular if and only if S(x) is slender.     

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.     

A simplified proof of parikh's theorem

A strengthened form of the pumping lemma for context-free languages is used to give a simple proof of Parikh's Theorem.     

Monoides pointes

We introduce here objects which appear naturally in the study of the syntactic monoids of non rational languages: the pairs consisting of a monoid together with a distinguished subset. Elementary properties of syntactic monoids are derived from theorems of universal algebra on the objects. Monoids with a distinguished subset define an equivalence relationship on formal languages: the classes of rational and context-free languages are considered with respect to this equivalence relationship. Eilenberg's theorem of varieties is expressed within this framework.      

一类吸引子的语法复杂性*

本文研究了Feigenbaum吸引子和周期窗口中Feisenbaum吸引子决定的形式语言,讨论了它们的语法复杂性.证明了这类吸引子都是ETOL语言,从而是上下文有关语言(CSL);而不是上下文无关语言(CFL).     

A KAM theorem for space-multidimensional Hamiltonian PDEs

We describe a method of translating a Lambek grammar with one division into an equivalent context-free grammar whose size is bounded by a polynomial in the size of the original grammar. Earlier constructions by Buszkowski and Pentus lead to exponential growth of the grammar size.     

The power of programmed grammars with graphs from various classes

Programmed grammars, one of the most important and well investigated classes of grammars with context-free rules and a mechanism controlling the application of the rules, can be described by graphs. We investigate whether or not the restriction to special classes of graphs restricts the generative power of programmed grammars with erasing rules and without appearance checking, too. We obtain that Eulerian, Hamiltonian, planar and bipartite graphs and regular graphs of degree at least three are pr-universal in that sense that any language which can be generated by programmed grammars (with erasing rules and without appearance checking) can be obtained by programmed grammars where the underlying graph belongs to the given special class of graphs, whereas complete graphs, regular graphs of degree 2 and backbone graphs lead to proper subfamilies of the family of programmed languages.     

A left part theorem for grammatical trees

A simple left part property for a set of grammatical trees is introduced. The class of left part grammars, a subclass of the class of context-free grammars, is defined. It is shown that the set of grammatical trees of a context-free grammar satisfies this left part property if and only if the context-free grammar is a left part grammar. Some properties of leftpart grammars are considered.     

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.     

A large neighbourhood search approach to the multi-activity shift scheduling problem

The challenge in shift scheduling lies in the construction of a set of work shifts, which are subject to specific regulations, in order to cover fluctuating staff demands. This problem becomes harder when multi-skill employees can perform many different activities during the same shift. In this paper, we show how formal languages (such as regular and context-free languages) can be enhanced and used to model the complex regulations of the shift construction problem. From these languages we can derive specialized graph structures that can be searched efficiently. The overall shift scheduling problem can then be solved using a Large Neighbourhood Search. These approaches are able to return near optimal solution on traditional single activity problems and they scale well on large instances containing up to 10 activities.     

Preface

The following morphic characterization of EOL languages is established. The family of EOL languages equals the family of all languages of the form h(L∩R) where h is a morphism, R is a regular language and L is the maximal solution of an equation $\text{?(X) = g(X)}$, where ? is a morphism, g is a coding and X is a language variable. It is shown that if g is allowed to be a weak coding, then a larger family of languages is obtained, which however is strictly contained in the family of ETOL languages.     

Bounded Discrete Holomorphic Functions on the Hyperbolic Plane

It is shown that, for the discretization of complex analysis introduced earlier by S. P. Novikov and the present author, there exists a rich family of bounded discrete holomorphic functions on the hyperbolic (Lobachevsky) plane endowed with a triangulation by regular triangles whose vertices have even valence. Namely, it is shown that every discrete holomorphic function defined in a bounded convex domain can be extended to a bounded discrete holomorphic function on the whole hyperbolic plane so that the Dirichlet energy be finite.