One way finite visit automata

A one-way preset Turing machine with base L is a nondeterministic on-line Turing machine with one working tape preset to a member of L. FINITEREVERSAL($\text{L}$) (FINITEVISIT ($\text{L}$)) is the class of languages accepted by one-way preset Turing machines with bases in $\text{L}$ which are limited to a finite number of reversals (visits). For any full semiAFL $\text{L}$, FINITEREVERSAL ($\text{L}$) is the closure of $\text{L}$ under homomorphic replication or, equivalently, the closure of $\text{L}$ under iteration of controls on linear context-free grammars while FINITEVISIT ($\text{L}$) is the result of applying controls from $\text{L}$ to absolutely parallel grammars or, equivalently, the closure of $\text{L}$ under deterministic two-way finite state transductions. If $\text{L}$ is a full AFL with $\text{L}$ ≠ FINITEVISIT($\text{L}$), then FINITEREVERSAL($\text{L}$) ≠ FINITEVISIT($\text{L}$). In particular, for one-way checking automata, k + 1 reversals are more powerful than k reversals, k + 1 visits are more powerful than k visits, k visits and k + 1 reversals are incomparable and there are languages definable within 3 visits but no finite number of reversals. Finite visit one-way checking automaton languages can be accepted by nondeterministic multitape Turing machines in space log₂n. Results on finite visit checking automata provide another proof that not all context-free languages can be accepted by one-way nonerasing stack automata.     

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.     

Abstract families of context-free grammars

An abstract family of grammars (AFG) may be defined as a class of grammars for which the corresponding class of languages forms an abstract family of languages (AFL) as defined by Ginsburg and Greibach. The derivation bounded grammars of Ginsburg and Spanier is an example of an AFG which is properly included in the class of all context-free grammars (also AFG). The main result is that there exist two distinct infinite hierarchies of AFG which exhaust the derivation bounded AFG such that the AFL associated with the kth member of one of these AFG hierarchies is properly included in the AFL associated with the k-lst member of that same hierarchy. Each hierarchy is shown to be strongly incomparable to the other; that is, the first member of each generates some language not generated by a fixed but arbitrary member of the other. We designate these hierarchies as the hierarchies of left and right dominant grammars (languages)     

Control sets on grammars using depth-first derivations

Control sets on grammars are extended to depth-first derivations. It is proved that a context-free language is generated by the depth-first derivations of an arbitrary context-free grammar controlled by an arbitrary regular set. This result is sharpened to obtain a new characterization of the family of derivation-bounded languages: a languageL is derivation bounded if and only if it is generated by the depth-first derivations of a context-free grammarG controlled by a regular subsetR of the Szilard language ofG. The left-derivation-bounded languages are characterized analogously using leftmost derivations. It is proved that a grammarG is nonterminal bounded if and only if the Szilard language defined using only the depth-first derivations ofG is regular. Finally, it is proved that if a family of languagesC is a trio, a semi-AFL, an AFL, or an AFL closed under -free substitution, then the family of languages generated using arbitrary context-free grammars controlled by members ofC is full, is closed under reversal, and has the closure properties assumed ofC.     

Stochastic grammars and languages

This paper summarizes some recent results concerned with the extension of formal languages to their corresponding stochastic versions. Weighted grammars and languages are first defined, and stochastic grammars and languages are defined as a special case of weighted grammars and languages. Fuzzy grammars and languages, which have some properties similar to weighted grammars and languages, are also discussed. Stochastic automata are defined from the language recognition viewpoint. Languages accepted by stochastic finite-state and pushdown automata, with and without a cutpoint, are studied. Weighted and stochastic programmed and indexed grammars, and stochastic nested stack automata are defined. Finally, some decidability problems of stochastic (weighted, fuzzy) languages are discussed, and problems for further research are suggested.This work was supported by the National Science Foundation Grant GK-18225.     

On ET0L Systems with rank

The notion of an ET0L system with rank is defined. It naturally extends already studied notions of a D0L system with rank and of an ET0L system of finite index. It turns out that in this way one gets an infinite hierarchy of classes of languages (each one being a full AFL) within the class of ET0L languages. This hierarchy starts with the class of ET0L languages of finite index and it fills in the class of nonexpansive ET0L languages. Some other properties of the class of ET0L systems with rank are also studied.     

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.     

The complexity of the membership problem for some extensions of context-free languagest†

The time and tape complexity of some families of languages defined in the literature by altering methods of generation by context-free grammars is considered. Specifically; it is shown that the following families of languages can be recognized by deterministic multitape Turing machines either in polynomial time or within (log n)² tape:

1) the context independent developmental (EOL) languages;

2) the simple matrix languages;

3) the languages generated by derivation restricted state grammars.:

4) the languages generated by linear context-free grammars with certain non-regular control sets;

5) the languages generated by certain classes of vector grammars.

In fact, these languages are of the same tape complexity as context-free languages. Other results indicate the complexity of EDOL languages and the effects on complexity of applying the homomorphic replication operator to regular and context-free languages.     

Automata theory based on lattice-ordered semirings

In this paper, definitions of K{\mathcal{K}} automata, K{\mathcal{K}} regular languages, K{\mathcal{K}} regular expressions and K{\mathcal{K}} regular grammars based on lattice-ordered semirings are given. It is shown that K{\mathcal{K}}NFA is equivalent to K{\mathcal{K}}DFA under some finite condition, the Pump Lemma holds if K{\mathcal{K}} is finite, and Ke{{\mathcal{K}}}\epsilonNFA is equivalent to K{\mathcal{K}}NFA. Further, it is verified that the concatenation of K{\mathcal{K}} regular languages remains a K{\mathcal{K}} regular language. Similar to classical cases and automata theory based on lattice-ordered monoids, it is also found that K{\mathcal{K}}NFA, K{\mathcal{K}} regular expressions and K{\mathcal{K}} regular grammars are equivalent to each other when K{\mathcal{K}} is a complete lattice.     

On the pre-AFL of [log n] space and related families of languages

New insight into the 1965 conjecture of Lewis et al., that some Context-Free Languages (CFLs) require more than [log n] space for recognition on off-line Turing machines, is derived from an examination of the pre-AFL properties of [log n] space. General results about related AFLs are used to reduce this conjecture to the questions of whether the [log n] class is an AFL and of whether [log n] recognition is a decidable question for certain related AFLs. One of these is the AFL generated by the [log n] class itself, which AFL is shown to properly contain all CFLs (Theorem 1) and, also, to be generated via length-preserving homomorphisms from the [log n] class, using the result that the latter is a pre-AFL (Theorem 2).An example of a related family, which happens to be contained in this newly studied AFL, is the principal AFL, Q, of quasi-real-time languages. Also, the open question of whether [log n] space is the same deterministically or nondeterministically is related to the above questions.     

Nonterminal complexity of tree controlled grammars

This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.     

PROBABILISTIC MACHINES AND LANGUAGES

In the past several years, there has been an increasing interest in the study of probabilistic machines, grammars, and families of languages associated with these machines and/or grammars. However, until now, the emphasis has been placed on the study of the structures of the particular probabilistic machines, grammars, and/or families of languages.

The main objective of the present paper is to develop a general treatment for probabilistic machines and languages. A formulation of an abstract model of probabilistic machines is presented. Various families of random languages associated with this model of probabilistic machines are studied and characterized. Since the model is general enough to encompass all existing types of probabilistic machines, the results obtained in this paper includes many of the known results as special cases. They also provide insights to the underlying structures of probabilistic machines and languages.     

On some families of languages related to developmental systems

OL systems and TOL systems are the simplest mathematical models for the study of the development of biological organisms with or without a variable environment, respectively. This paper contributes to the study of the properties of the languages generated by these systems and by their generalizations. Macro OL (TOL) languages are languages obtained by substituting languages of a given type in OL (TOL) languages. We study properties of certain families of macro OL (TOL) languages in particular we show that they are full AFL's.

We observe that OL, TOL systems and many of their generalizations can be viewed as special classes of index grammars.     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

Chains of full AFL's

If a full AFL is not closed under substitution, then ô , the result of substituting members of into, is not substitution closed and hence generates an infinite hierarchy of full AFL's. If ₁ and ₂ are two incomparable full AFL's, then the least full AFL containing ₁ and ₂ is not substitution closed. In particular, the substitution closure of any full AFL properly contained in the context-free languages is itself properly contained in the context-free languages. If any set of languages generates the context-free languages, one of its members must do so. The substitution closure of the one-way stack languages is properly contained in the nested stack languages. For eachn, there is a class of full context-free AFL's whose partial ordering under inclusion is isomorphic to the natural partial ordering onn-tuples of positive integers.This paper was completed while the author was in the Division of Engineering and Applied Physics of Harvard University. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under contracts F-1962870C0023 and F-1962868C0029, and by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR Grant No. AF-AFOSR-1203-67A and the Division of Engineering and Applied Physics of Harvard University.     

Morphismes et bimorphismes d'arbres

For every pair of positive integers n and p, there is a language accepted by a real-time deterministic pushdown automaton with n states and p stack symbols and size O(np), for which every context-free grammar needs at least n²p+1 nonterminals if n>1 (or p non-terminals if n = 1). It follows that there are context-free languages which can be recognized by pushdown automata of size O(np), but which cannot be generated by context-free grammars of size smaller than O(n²p); and that the standard construction for converting a pushdown automaton to a context-free grammar is optimal in the sense that it infinitely often produces grammars with the fewest number of nonterminals possible.     

Team Learning of Computable Languages

A team of learning machines is a multiset of learning machines. A team is said to learn a concept successfully if each member of some nonempty subset, of predetermined size, of the team learns the concept. Team learning of languages may be viewed as a suitable theoretical model for studying computational limits on the use of multiple heuristics in learning from examples. Team learning of recursively enumerable languages has been studied extensively. However, it may be argued that from a practical point of view all languages of interest are computable. This paper gives theoretical results about team learnability of computable (recursive) languages. These results are mainly about two issues: redundancy and aggregation. The issue of redundancy deals with the impact of increasing the size of a team and increasing the number of machines required to be successful. The issue of aggregation deals with conditions under which a team may be replaced by a single machine without any loss in learning ability. The learning scenarios considered are: (a) Identification in the limit of grammars for computable languages. (b) Identification in the limit of decision procedures for computable languages. (c) Identification in the limit of grammars for indexed families of computable languages. (d) Identification in the limit of grammars for indexed families with a recursively enumerable class of grammars for the family as the hypothesis space. Scenarios that can be modeled by team learning are also presented. Received March 1998, and in final form January 1999.     

A note on Lindenmayer systems,Szilard languages,spectra, and equivalence

We investigate the Szilard languages and the spectra of Lindenmayer systems through the generalization of Lindenmayer systems toK-iteration grammars and context-sensitiveK-iteration grammars. Various decidability and undecidability results are presented with respect to the evaluation of Szilard languages and spectra for particularK-iteration grammars. Further, two different definitions of the Szilard and spectral equivalence of twoK-iteration grammars are investigated.Work carried out under a National Research Council of Canada Grant No. A-7700.     

Iterated deterministic substitution

Summary Deterministic substitution of languages means substituting the same word (from a given language) for all occurrences of a symbol. For an arbitrary family K of languages the notion of deterministic K-iteration grammar is introduced, which is essentially the iteration of a finite number of deterministic substitutions of languages from K. The families of languages generated by these grammars are investigated.The work of the first author has been supported by the Netherlands Organization for the Advancement of Pure Research (Z.W.O.)