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.     

A useful lemma for context-free programmed grammars

We show that all quasi-realtime one-way multi-counter languages can be generated by a context-free -free programmed grammar (even under the free interpretation). The result can be used to obtain a new and almost trivial proof of the fundamental theorem that arbitrary context-free programmed grammars can generate all recursively enumerable languages. The proof of our result also yields the following, interesting characterization: the quasi-realtime one-way multi-counter languages are precisely the -limited homomorphic images of (free) context-free programmed production languages. It follows that the (free) derivation languages of context-free or even context-free programmed grammars, which were known to be context-sensitive, are in fact contained in the family of context-free -free programmed languages.     

Time-bounded controlled bidirectional grammars

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions..     

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.     

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.     

On the generative power of sequential and parallel programmed graph grammars

Programmed graph grammars are formally introduced and their generative power is investigated. Programmed graph grammars differ from other approaches to graph grammars in the so-called control diagram which controls the application order of productions. Restricting the form of the productions of a programmed graph grammar we get several classes of graph languages. These are compared mutually as well as with the hierarchy introduced by Nagl [18]. For unrestricted and monotone productions corresponding classes of graph languages coincide, while the class of context free programmed graph languages is properly contained in the class of context free graph languages in the sense of [18].     

Size,index, and context-sensitivity of controlled partition grammars

Controlled partition grammars (CPGs) were designed to apply to certain needs of linguists. General CPGs generate exactly all context-sensitive languages. CPGs have two parameters:size andindex. The partition index of CPGs can be bounded by two, while CPGs with partition index one generate exactly the class of context-free languages. The size (of the partition blocks) of CPGs can be bounded by two, while CPGs of size one generate a class of languages properly contained in the class of contextsensitive languages. If one can eliminate recursive productions of the formAB in a CPG then deterministic and nondeterministic lba's are equivalent.This author was supported in part by NSF Grant No. MCS 76-10076.This author was supported in part by NSF Grant No. MCS 75-22557.     

Optimal probabilistic evaluation functions for search controlled bystochastic context-free grammars

The possibility of using stochastic context-free grammars (SCFG's) in language modeling (LM) has been considered previously. When these grammars are used, search can be directed by evaluation functions based on the probabilities that a SCFG generates a sentence, given only some words in it. Expressions for computing the evaluation function have been proposed by Jelinek and Lafferty (1991) for the recognition of word sequences in the case in which only the prefix of a sequence is known. Corazza et al. (1991) have proposed methods for probability computation in the more general case in which partial word sequences interleaved by gaps are known. This computation is too complex in practice unless the lengths of the gaps are known. This paper proposes a method for computing the probability of the best parse tree that can generate a sentence only part of which (consisting of islands and gaps) is known. This probability is the minimum possible, and thus the most informative, upper-bound that can be used in the evaluation function. The computation of the proposed upper-bound has cubic time complexity even if the lengths of the gaps are unknown. This makes possible the practical use of SCFG for driving interpretations of sentences in natural language processing     

From controlled dynamical systems to context-dependent grammars: A connectionist approach

Formal language techniques may be used to study controlled dynamical systems and lead to a formulation in terms of context-dependent grammars. Using automata as basic units we obtain an on-line implementation of the grammars. The implementation has a hierarchical structure, the lowest level dealing with the identification of alphabet symbols (terminal and non-terminal), and the other with the establishment of the grammar productions. The method provides an automatic construction of the automata network from the experimental data. In particular, the parallel-processing capabilities of automata networks improves the performance of grammar-based models for control and anomaly detection in electromechanical devices of industrial relevance. One such example is presented.     

Apex graph grammars and attribute grammars

Summary Apex graph grammars are a particular type of directed node-label controlled (DNLC) graph grammars: the embedding edges are established between terminal nodes only. Apex graph grammars, slightly generalized, can generate the sets of dependency graphs of attribute grammars. The other way around, every apex graph language can be obtained from such a dependency graph language by a graph replacement (which is an operation analogous to a string homomorphism).     

A characterization of context-free string languages by directed node-label controlled graph grammars

Summary Directed node-label controlled graph grammars (DNLC grammars) are sequential graph rewriting systems. In a direct derivation step of a DNLC grammar a single node is rewritten. Both the rewriting of a node and the embedding of a daughter graph in a host graph are controlled by the labels of nodes only. We study the use of those grammars to define string languages. In particular we provide a characterization of the class of context-free string languages in terms of DNLC grammars.     

Extending Lambek grammars to basic categorial grammars

Pentus (1992) proves the equivalence of LCG's and CFG's, and CFG's are equivalent to BCG's by the Gaifman theorem (Bar-Hillel et al., 1960). This paper provides a procedure to extend any LCG to an equivalent BCG by affixing new types to the lexicon; a procedure of that kind was proposed as early, as Cohen (1967), but it was deficient (Buszkowski, 1985). We use a modification of Pentus' proof and a new proof of the Gaifman theorem on the basis of the Lambek calculus.     

One-sided forbidding grammars and selective substitution grammars

In one-sided forbidding grammars, the set of rules is divided into the set of left forbidding rules and the set of right forbidding rules. A left forbidding rule can rewrite a non-terminal if each of its forbidding symbols is absent to the left of the rewritten symbol in the current sentential form, while a right forbidding rule is applied analogically except that this absence is verified to the right. Apart from this, they work like ordinary forbidding grammars. As its main result, this paper proves that one-sided forbidding grammars are equivalent to selective substitution grammars. This equivalence is established in terms of grammars with and without erasing rules. Furthermore, this paper proves that one-sided forbidding grammars in which the set of left forbidding rules coincides with the set of right forbidding rules characterize the family of context-free languages. In the conclusion, the significance of the achieved results is discussed.     

Commutative grammars

Commutative grammars are a formalism for generating bags, equivalent to vector addition systems and Petri nets. Known results are recalled and new one are presented on reachability and boundedness. In particular some subclasses of commutative grammars are introduced which admit a positive answer to these problems, and generate semilinear languages. Finally the equivalence, via Parikh mapping, of commutative and matrix grammars is proven.     

Ll-regular grammars

Culik II and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars.

In this paper we consider an analogous extension of the LL(k) grammars called the LL- regular grammars. The relation of this class of grammars to other classes of grammars will be shown. Any LL-regular grammars is an LR-regular grammar. Properties of LL(k) grammars can be generalized to properties of LL-regular grammars.