Surface tree languages and parallel derivation trees

The surface tree languages obtained by top-down finite state transformation of monadic trees are exactly the frontier-preserving homomorphic images of sets of derivation trees of ETOL systems. The corresponding class of tree transformation languages is therefore equal to the class of ETOL languages.     

A note on a family of acceptors for some families of developmental languages†

In a previous paper Rozenberg (1974) introduced the PDAC acceptors (pushdown-array-of-counters acceptors) and showed that the restricted PDACA characterize the EOL languages. In this present note the PDAPDA (pushdown-array-of-pushdowns acceptors) are introduced and it is shown that the restricted PDA² characterize the ETOL languages.     

Three hierarchies of transducers

Composition of top-down tree transducers yields a proper hierarchy of transductions and of output languages. The same is true for ETOL systems (viewed as transducers) and for two-way generalized sequential machines.     

Iterating iterated substitution

By iterating iterated substitution not all regular languages can be copied. Hence the smallest full hyper (1)-AFL is properly contained in ETOL, the smallest full hyper-AFL. The number of iterations of iterated substitution gives rise to a proper hierarchy. Consequently the smallest full hyper (1)-AFL is not a full principal AFL.     

Decidable properties of monadic recursive schemas with a depth parameter

Summary Monadic table counter schemas (MTCS) are defined as extensions of recursive monadic schemas by incorporating a depth-of-recursion counter. The family of languages generated by free MTCS under Herbrand interpretation is shown to be the family of ETOL languages. It is proven that the halting and divergence problems are decidable for free MTCS and that the freedom problem is decidable. Most of these results are obtained using results on regular control sequences from L system theory.     

Tree controlled grammars

Languages are studied which can be generated by context-free grammars under a single simple restriction which must be satisfied by its derivation trees. Using tree controlled grammars (TC grammars for short) all unambigous and some inherently ambigous context-free languages, and also some non context-free languages can be parsed in timeO(n ²). The classes of regular, linear, context-free, EOL, ETOL and type 0 languages can be characterized in a natural manner using TC grammars. A context-free generator for all type 0 languages is exhibited. Some normal forms for TC grammars are established but it is shown that many common normal forms (e. g. Greibach normal form) cannot be obtained for TC grammars in general.     

Teams in cooperating grammar systems

Abstract

We consider grammar systems in which several components are active at the same moment (a team of components is working). The power of such mechanisms is investigated and it is found that in many cases the team feature increases the generative capacity of grammar systems. In the so-called t-mode of derivation (a team works as much as it can) it is found that the team size does not induce an infinite hierarchy of languages. However, the family obtained in this case is a full abstract family of languages properly including ETOL.     

On the structure of derivations in deterministic ET0L systems

This paper investigates the structure of derivations in deterministic ET0L systems. The main theorem says that in a deterministic ETOL system each derivation of a long enough word of a special kind (the so-called f-random word) has a rather strong combinatorial structure. In fact the main result of this paper is essential for proving some useful properties of ET0L languages which is demonstrated in a number of papers.     

On good ETOL forms

This paper continues the study of ETOL forms and good EOL forms done by Maurer, Salomaa and Wood. It is proven that binary very complete ETOL forms exist, good synchronized ETOL forms exist and that no propagating or synchronized ETOL form can be very complete.     

Context-free grammars with selective rewriting

Summary Selective substitution grammars first introduced by Rozenberg are further investigated. In particular we study context-free grammars with selection, since the original model is too general in its generative power. It is shown how the families of context-free, EOL and ETOL languages can be characterized by selective context-free grammars. Further the effect of linguistic restrictions on the family of selection languages is investigated. Finally, the notion of a universal grammar is investigated in this framework, demonstrating the existence of selection universal grammars under weak conditions on the selection family.Work supported partially by a Natural Sciences and Engineering Research Council of Canada grant No. A-7700 and partially by the Universitaire Instelling Antwerpen     

On non context-free grammar forms

A grammar formF defines via a so-calledinterpretation mechanism, a family of languages(F). In this paper we establish that for many grammar formsF, (the family of context-free languages) implies(F)= _RE (the family of recursively enumerable sets). We conjecture that this is also true in general. Because of this, it seems necessary to use restricted interpretations for non context-free grammar forms, a form giving then rise to a family We compare the obvious alternatives for restricting interpretations and focus attention on two promising alternatives, _Q (_F) and _st(F) and their combination _{Q, st}(F). Using st-interpretations, surprising families can be generated and strong normal form results can be obtained. Closure results and decidability results are also given. UnderQ, st-interpretation, it is possible to characterize a number of well-known families of languages between _CF and _RE, including the families of EOL, ETOL, matrix and scattered context languages.Part of this work was carried out while the third and fourth authors were visiting the University of Karlsruhe. Part of this work was supported by the Natural Sciences and Engineering Research Council of Canada Grant No. A-7700.     

A note on language equations involving morphisms

Language equations, ETOL systems, L systems     

Extended macro grammars and stack controlled machines

K-extended basic macro grammars are introduced, where K is any class of languages. The class B(K) of languages generated by such grammars is investigated, together with the class LB(K) of languages generated by the corresponding linear basic grammars. For any full semi-AFL K, B(K) is a full AFL closed under iterated LB(K)-substitution, but not necessarily under substitution. For any machine type D, the stack controlled machine type corresponding to D is introduced, denoted S(D), and the checking-stack controlled machine type CS(D). The data structure of this machine is a stack which controls a pushdown of data structures from D. If D accepts K, then S(D) accepts B(K) and CS(D) accepts LB(K). Thus the classes B(K) are characterized by stack controlled machines and the classes LB(K), i.e., the full hyper-AFLs, by checking-stack controlled machines. A full basic-AFL is a full AFL K such that B(K) ? K. Every full basic-AFL is a full hyper-AFL, but not vice versa. The class of OI macro languages (i.e., indexed languages, i.e., nested stack automaton languages) is a full basic-AFL, properly containing the smallest full basic-AFL. The latter is generated by the ultrabasic macro grammars and accepted by the nested stack automata with bounded depth of nesting (and properly contains the stack languages, the ETOL languages, i.e., the smallest full hyper-AFL, and the basic macro languages). The full basic-AFLs are characterized by bounded nested stack controlled machines.     

An Inverse Homomorphic Characterization of Full Principal AFL

The main result of this paper is: Let L be a full principal AFL closed under context-free substitution. Then there is a fixed language l₀ in L such that for each L in L there exist a weak coding h and a homomorphism g such that L = hg^?1(L₀). As a corollary, it immediately follows that there is a fixed ETOL language L₀ such that for each ETOL language L there exist a weak coding h and a homomorphism g such that L = hg^?1(L₀).     

Completions in measure of languages and related combinatorial problems

We consider measures of languages induced by Bernoulli distributions on the letters of a given alphabet. Of particular interest are languages having a measure equal to 1 with respect to all positive Bernoulli distributions (Bernoulli sets). The main object of the paper is to study conditions ensuring that a given language has a finite Bernoulli completion, i.e., it is included in a finite Bernoulli set. Some characterizations of languages having finite Bernoulli completions are given. In the case of a two-letter alphabet it is shown that one can decide whether a finite language has a finite Bernoulli completion or not. Moreover, any finite code over a two-letter alphabet has a finite Bernoulli completion. Finally, we prove that two finite languages have the same measure with respect to all Bernoulli distributions if and only if each of the two languages can be obtained from the other by using a finite number of times three suitable measure-invariant transformations.     

Vectorial languages and linear temporal logic

Determining for a given deterministic complete automaton the sequence of visited states while reading a given word is the core of important problems with automata-based solutions, such as approximate string matching. The main difficulty is to do this computation efficiently. Considering words as vectors and working on them using vectorial operations allows to solve the problem faster than using local operations.

In this paper, we show first that the set of vectorial operations needed by an algorithm representing a given automaton depends on the language accepted by the automaton. We give precise characterizations for star-free, solvable and regular languages using vectorial algorithms. We also study classes of languages associated with restricted sets of vectorial operations and relate them with languages defined by fragments of linear temporal logic.

Finally, we consider the converse problem of constructing an automaton from a given vectorial algorithm. As a byproduct, we show that the satisfiability problem for some extensions of LTL characterizing solvable and regular languages is PSPACE-complete.     

On inverse deterministic pushdown transductions

Classes of source languages which can be mapped by a deterministic pushdown (DPDA) transduction into a given object language (while their complement is mapped into the complement of the object language) are studied. Such classes of source languages are inverse DPDA transductions of the given object language. Similarly for classes of object languages. The inverse DPDA transductions of the Dyck sets are studied in greater detail: they can be recognized in deterministic storage (log n)' but do not comprise all context free languages; their emptiness problem is unsolvable and their closure under homomorphism constitutes the r.e. sets. For each object language L we can exhibit a storage hardest language for the class of inverse DPDA transductions of L; similarly for the classes of regular, deterministic context free, and context free object languages. Last, we classify the classes of inverse DPDA transductions of the regular, deterministic context free, context free and deterministic context sensitive languages.     

A grammatical inference for harmonic linear languages

We propose an effective algorithm to infer linear grammars from given finite sample sets. It is shown that the algorithm is complete for harmonic linear languages being a superclass of regular languages. A necessary and sufficient condition under which the algorithm converges to an expected grammar is given.     

(DNA) computing by carving

 Inspired by the experiments reported recently in the emerging area of DNA computing, we consider a somewhat unusual type of a computation strategy: generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. We call this a computation by carving. This leads both to a speculation with possible important consequences and to interesting theoretical computer science (formal language) questions. The speculation is that in this way we can “compute” non-recursively enumerable languages, because the family of recursively enumerable languages is not closed under complementation. The formal language theory questions concern sequences of languages with certain regularities, needed as languages to be extracted from the total language of candidate solutions of a problem. Specifically, we consider sequences of languages obtained by starting from a given regular language and iteratively applying to it a given finite state sequential transducer (a gsm). Computing by carving with respect to such a sequence of languages can identify all context-sensitive languages and can also lead to non-recursively enumerable languages (but not all recursively enumerable languages can be obtained in this way). In practical circumstances, the carving process should be finite, hence, in general, approximations of the desired language are obtained. We also briefly discuss this aspect.     

Formal power series and regular operations on fuzzy languages

In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series.