We propose a generalization of the notion "deterministic" to "l-r-deterministic" for descending tree automata (also called root-to-frontier). The corresponding subclass of recognizable tree languages is characterized by a structural property that we name "homogeneous." Given a descending tree automaton recognizing a homogeneous tree language, it can be left-to-right (l-r) determinized and then minimized. The obtained minimal l-r-deterministic tree automaton is characterized algebraically. We exhibit a formal correspondence between the two evaluation modes on trees (ascending and descending) and the two on words (right-to-left and left-to-right). This is possible by embedding trees into the free monoid of pointed trees. We obtain a unified view of the theories of minimization of deterministic ascending and l-r-deterministic descending tree automata.

We study some properties of array grammars, called puzzle grammars, introduced in Ref. 7. We give a new method, using puzzle grammar, for generating the set of rectangles. We prove that the emptiness problem for puzzle grammar is undecidable. We show that the non-overlapping problem for puzzle grammar is decidable.

We investigate the complexity of the recognition of images generated by a class of context-free image grammars. We show that the sequential time complexity of the recognition of an n × n image as generated by a context-free grammar is O(nM(n)), where M(n) is the time to multiply two boolean n × n matrices. The space complexity of this recognition is O(n3). Using a parallel random access machine (i.e. PRAM), the recognition can be done in O( log 2(n)) time with n7 processors or in O(n log 2(n)) time with n6 processors. We also introduce high dimensional context-free grammars and prove that their recognition problem is polylogarithmic.

We introduce a new model for generating finite, digitized, connected pictures called puzzle grammars and study its generative power by comparison with array grammars. We note how this model generalizes the classical Chomskian grammars and study the effect of direction-independent rewriting rules. We prove that regular control does not increase the power of basic puzzle grammars. We show that for basic and context-free puzzle grammars, the membership problem is NP-complete and the emptiness problem is undecidable.

No abstract available.

We define a syntactic model for generating sets of images, where an image can be viewed as an array over finite alphabet. This model is called image grammar. Image grammar can be considered as a generalization of classical Chomsky grammar. Then we study some combinatorial and language theoretical properties such as reduction, pumping lemmas, complexity measure, we give a strict infinite hierarchy. We also characterize these families in terms of deterministic substitutions and Chomsky languages.

The purpose of automata theory is to study and classify those properties of words that may be defined by a finite structure, say a finite automaton or a finite monoid. It seems natural to consider the same problem for infinite words. This amounts to studying the asymptotic behaviour of finite automata. As is well-known, this breaks the equivalence between determinism and non-determinism of finite automata.

With every language L we associate an increasing function called its rational index. We obtain this function by comparing L with rational languages of increasing complexity. We show that the rational indices of two languages related by a rational transduction are polynomially related. From this, we can define new rational cones of languages in terms of rational indices. We then focus our attention on the rational index of context-free languages and raise several questions closely related to the open problems concerning the subcones of the family of context-free languages.

In this paper we study bijective a-transducers. We derive necessary and sufficient conditions on pairs of regular sets (R,S) such that a bijective a-transducer, mapping R cnto S exists. The results obtained allow the systematic construction of an a-transducer, mapping a set R onto a set S bijectively for surprisingly "different" regular sets R and S.

The intersection closure and the closure under homomorphic replication and intersection of certain classes of languages are studied and related to a specific class $\mathcal{L}_{{\text{BNP}}} $ of languages defined in [5]. The proof techniques rely on the “set-theoretic algebra” of language theory instead of arguments involving abstract families of acceptors.

To each family C of interpretations corresponds an equivalence relation among program schemes, namely the equivalence of the program schemes for all interpretation of C. A family C is algebraic if any two programs are C-equivalent iff every partial finite computation of one of them is C-equivalent to some partial finite computation of the other. Our main theorem states that a family C is algebraic iff it is represented with respect to the equivalence of programs by a single interpretation (a C-Herbrand interpretation) which is algebraic (in Scott's sense, roughly speaking). We give examples of algebraic and non algebraic families.

The purpose of this paper is to establish the following result.

A Turing machine whose behavior is restricted so that each read-write head can change its direction only a bounded number of times is reversal-bounded. Here we consider nondeterministic multitape acceptors which are both reversal-bounded and also operate in linear time. Our main result shows that such an acceptor need have only three pushdown stores as auxiliary storage, each pushdown store need make only one reversal, and the acceptor can operate in real time.

@ by the n relations xixi = 1 i e {1,...,n}. The author convinced himself that many other congruences have the same property [Ni 1], and undertook the task of finding them systematically. Here is presented a part of the results of this undertaking. An important family of congruences is brought to light which have interesting decidability properties: in the constructions leading to these decidability properties we used as a guide line the nice paper of Mac Naughton [McN]. Sufficient conditions are given in order that the equivalence classes (and their complements) of such a congruence be an algebraic language. We do not study in this paper the properties of these languages, this will be done elsewhere [Ni 2].