Lower bounds for context-free grammars

Ellul, Krawetz, Shallit and Wang prove an exponential lower bound on the size of any context-free grammar generating the language of all permutations over some alphabet. We generalize their method and obtain exponential lower bounds for many other languages, among them the set of all squares of given length, and the set of all words containing each symbol at most twice.     

A unifying approach to picture grammars

Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using an approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling, named regional, and define the corresponding regional tile grammars. They include both Siromoney?s (or Matz?s) Kolam grammars and their generalization by Pr?ša, as well as Drewes?s grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems).     

The language intersection problem for non-recursive context-free grammars

We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive.     

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.     

A note on a proposed LALR parser for extended context-free grammars

The lemma in “An improved LALR(k) parser generation for regular right part grammars” [Inform. Process. Lett. 47 (1993) 123-129] to test the applicability of the method is shown to be false by means of a counter-example grammar.     

On the relationship between the LL(k) and LR(k) grammars

In the literature various proofs of the inclusion of the class of LL(k) grammars into the class of LR(k) grammars can be found. Some of these proofs are not correct, others are informal, semi-formal or contain flaws. Some of them are correct but the proof is less straightforward than demonstrated here.     

Linearity and nondeletion on monadic context-free tree grammars

In this paper, subclasses of monadic context-free tree grammars (CFTGs) are compared. Since linear, nondeleting, monadic CFTGs generate the same class of string languages as tree adjoining grammars (TAGs), it is examined whether the restrictions of linearity and nondeletion on monadic CFTGs are necessary to generate the same class of languages.     

Two undecidability results for chain code picture languages

It is undecidable whether or not two 1-retreat-bounded regular languages describe exactly the same set of pictures or they describe a picture in common.     

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.     

A non-left-to-right,non-directional parser for ambiguous lattices

In syntactic pattern recognition the need of reducing computational power may require the use of more general parsers than the standard ones, allowing to efficiently exploit the structural knowledge for limiting the extraction of primitive patterns. In this paper a new flexible, non-directional, non-left-to-right parsing scheme is presented; it has worst case space complexity O(N²) and time complexity O(N³), where N is the length of the input string. These upper bounds are lowered for particular classes of context-free grammars as, for instance, linear or non-ambiguous ones.     

A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with a reduced number of both nonterminals and context-sensing productions.