Search

A Szilard language is a language theoretical tool used to describe the derivation process in a formal grammar or grammar system. We investigate computational resources used by (alternating) Turing machines to accept Szilard languages of Chomsky grammars, regulated grammars and grammar systems. The results are related to the circuit complexity classes NC1 and NC2. The paper is a survey of the most important complexity results in the field, but it also brings several new insights into the parallel complexity of Szilard languages of grammar systems. We focus on parallel communicating grammar systems (PCGSs) with context-free components, and we prove that the class of Szilard languages of centralized (returning or non-returning) PCGSs is included in NC1.

We study abstract interpretations of a fixpoint protoderivation semantics defining the maximal derivations of a transitional semantics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classical equational and derivational language semantics and including Knuth grammar problems, classical grammar flow analysis algorithms and parsing algorithms.

A variant of the Circuit Value Problem is introduced, in which every gate implements the NOR function @?([email protected]?y), and one of the inputs of every kth gate must be the (k-1)th gate. The problem, which remains P-complete, is encoded as a simple formal language over a two-letter alphabet, which can be succinctly represented by language equations of several types. Using this representation, a conjunctive grammar with 8 rules, a Boolean grammar with 5 rules and an LL(1) Boolean grammar with 8 rules for this language are constructed. Another encoding of the problem is represented by a trellis automaton with 11 states and a linear conjunctive grammar with 20 rules.

In this note, we bring to evidence some techniques that can be performed on PC grammar systems working with linear grammars. This allows us to show that the generative power of (centralized) PC grammar systems working with right-linear grammars is bigger than expected, and to prove closure properties of the families of languages generated by centralized PC grammar systems working with (right-)linear grammars, such as the closure under union and the closure under intersection with a rational set, and for centralized PC grammar systems working with right-linear grammars, the closure under product.

Plummer [A.R. Plummer, S4 enriched multimodal categorial grammars are context-free, Theoretical Computer Science 388 (2007) 173–180] showed that categorial grammars based on NLS4, the non-associative multimodal Lambek calculus enriched with S4 axioms, weakly recognize context-free languages. However, the proof contains a gap. We correct the earlier proof, utilizing a technique given in Buszkowski [W. Buszkowski, Lambek calculus with nonlogical axioms, in: C. Casadio, P.J. Scott, R.A.G. Seely (Eds.), Language and Grammar: Studies in Mathematical Linguistics and Natural Language, in: Lecture Notes, vol. 168, Center for the Study of Language and Information, Stanford, 2005, pp. 77–93]. This technique immediately proves that NLS4 is decidable in polynomial time.

An interpretation of a grammar form is called (k, i)-bounded iff all its nonterminals are substituted by at most k symbols and all its terminals are replaced by at most i words. The (k, i)-bounded grammar family of a grammar form is the collection of its (k, i)-bounded interpretations, and its (k, i)-bounded grammatical family is the corresponding family of languages. The paper gives basic properties of these families. Especially, we show the decidability of the equivalence problem for bounded grammar families, the undecidability of the membership problem for bounded language families and give some hierarchy, closure and descriptional complexity results. Finally, some consequences in normal form theory of context-free languages are presented.

We consider the problem of learning a context-free grammar from its structural descriptions. Structural descriptions of a context-free grammar are unlabelled derivation trees of the grammar. We present an efficient algorithm for learning context-free grammars using two types of queries: structural equivalence queries and structural membership queries. The learning protocol is based on what is called “minimally adequate teacher”, and it is shown that a grammar learned by the algorithm is not only a correct grammar, i.e. equivalent to the unknown grammar but also structurally equivalent to it. Furthermore, the algorithm runs in time polynomial in the number of states of the minimum frontier-to-root tree automaton for the set of structural descriptions of the unknown grammar and the maximum size of any counter-example returned by a structural equivalence query.

A method is presented for the elimination of null productions from a context-free grammar in such a way that the resulting grammar covers the original one, that is, the languages generated are the same and parses in the original grammar are homomorphic images of equivalent parses in the covering grammar. We show that in a natural subclass of covers, called the class of compatible covers, the method is best possible in the sense that a compatible cover with no null productions can be produced by the method if and only if such a cover exists. The use of the method in transformations for obtaining a cover in Greibach normal form is finally analyzed.

For any given binary relation ϱ defined on the context-free grammars, there is the associated computational problem of determining, for a pair of grammars ( G , H ), if G ϱ H . We study the complexity of this problem for a number of grammatical similarity relations whose definitions involve mappings between the symbols of related grammars. The relations considered include Reynolds covering, weak Reynolds covering, onto grammar homomorphism, grammar isomorphism, interpretation of grammar forms, and weak interpretation of grammar forms. A single general theorem is used to show that the computational problem associated with each of these grammatical relations, except grammar isomorphism, is NP-complete. In contrast, deterministic polynomial time algorithms are presented for testing if G ϱ H , when H is structurally unambiguous and the relation ϱ is Reynolds covering, onto grammar homomorphism, or grammar isomorphism. These results provide a rare example of a nontrivial natural algebraic and/or combinatorial structure, namely the unambiguous context-free grammars, with polynomial time algorithms for homomorphism, onto homomorphism, and isomorphism. We also show that the grammar isomorphism problem is polynomially equivalent to the graph isomorphism problem.

A 1S grammar generalizes a context-free grammar in the following way: a production A → α can be applied to a string uAv (to rewrite the designed occurence of A) provided that all letters from u belong to a fixed alphabet X and all letters from v belong to a fixed alphabet Z (the alphabets X and Z are independent of the production). It is proved that a language is generated by a 1S grammar if and only if it is context-free: this solves an open problem from the theory of selective substitution grammars (Kleijn and Rozenberg, 1981/82).

Pure grammars are grammars without non-terminals. In this paper we show as one main result that any two acyclic deterministic pure (dP) grammars that generate the same finite language are isomorphic. Furthermore, the notion of a pure grammar form is investigated. As the second main result we show that the form-equivalence problem for dP grammar forms is decidable.

A left-forbidding grammar, introduced in this paper, is a context-free grammar, where a set of nonterminal symbols is attached to each context-free production. Such a production can rewrite a nonterminal provided that no symbol from the attached set occurs to the left of the rewritten nonterminal in the current sentential form. The present paper discusses cooperating distributed grammar systems with left-forbidding grammars as components and gives some new characterizations of language families of the Chomsky hierarchy. In addition, it also proves that twelve nonterminals are enough for cooperating distributed grammar systems working in the terminal derivation mode with two left-forbidding components (including erasing productions) to characterize the family of recursively enumerable languages.

This paper deals with the problem of computing relations from their abstract non-algorithmic specifications. The formalism under consideration is that of two-level grammars, introduced originally for defining languages. In this formalism the intuitions behind the formal definition can be directly expressed by the grammatical rules, which may have a form close to the statements of natural language. A notion of the relation specified by a two-level grammar is introduced and computability of such relations is discussed. For a class of two-level grammars, called the transparent grammars, an algorithm is outlined for computing the relations specified by the grammars of this class. The transparent grammars turn out to be a generalization of the formalism of Horn clauses, and the algorithm is based on unification. The language generated by a two-level grammar can be used as an additional tool for controlling computations. A transparent two-level grammar can be considered as a non-algorithmic program specifying an input/output relation. The computational algorithm defines an operational semantics of such programs.

A new direct construction from a grammar to a realtime deterministic pushdown automation is presented. The grammar is required to be in a special form, but the construction is more natural than previously known constructions. As a result the family of stack uniform strict deterministic languages can be characterized by a grammar family.