Search

Approaches based on the idea generically called distributional learning have been making great success in the algorithmic learning of several rich subclasses of context-free languages and their extensions. Those language classes are defined by properties concerning string-context relation. In this paper, we present a distributional learning algorithm for conjunctive grammars with the k-finite context property (k- fcp ) for each natural number k. We also compare our result with the closely related work by Clark et al. (JMLR 2010) [5] on learning some context-free grammars using contextual binary feature grammars ( cbfg s). We prove that the context-free grammars targeted by their algorithm have the k- fcp . Moreover, we show that every exact cbfg has the k- fcp , too, while not all of them are learnable by their algorithm. Clark et al. conjectured a learning algorithm for exact cbfg s should exist. This paper answers their conjecture in a positive way.

Trees can be conveniently compressed with linear straight-line context-free tree grammars. Such grammars generalize straight-line context-free string grammars which are widely used in the development of algorithms that execute directly on compressed structures (without prior decompression). It is shown that every linear straight-line context-free tree grammar can be transformed in polynomial time into a monadic (and linear) one. A tree grammar is monadic if each nonterminal uses at most one context parameter. Based on this result, polynomial time algorithms are presented for testing whether a given (i) nondeterministic tree automaton or (ii) nondeterministic tree automaton with sibling-constraints or (iii) nondeterministic tree walking automaton, accepts a tree represented by a linear straight-line context-free tree grammar. It is also shown that if tree grammars are nondeterministic or non-linear, then reducing their numbers of parameters cannot be done without an exponential blow-up in grammar size.

Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols.

We consider the problem of inductively inferring a grammar for a language, given (positive) examples of the language and putative (possibly faulty) grammars for the complement of the language. The criterion of success is identification in the limit, defined by E. M. Gold (1967, Inform. and Control10, 447–474). Additional information is useful insofar as it allows the identification of language classes that would not be identified with positive examples alone. An infinite sequence of grammars past some finite position are correct for the complement of the input language, is not as useful a form of additional information as a single correct grammar for the complement. Grammars that are almost correct for the complement (that is, that make finitely many errors) are not as useful as correct grammars, and the usefulness of a grammar decreases with increasing numbers of errors.

We introduce the handle-rewriting hypergraph grammars (HH grammars), based on the replacement of handles, i.e., of subhypergraphs consisting of one hyperedge together with its incident vertices. This extends hyperedge replacement, where only the hyperedge is replaced. A HH grammar is separated (an S-HH grammar) if nonterminal handles do not overlap. The S-HH grammars are context-free, and the sets they generate can be characterized as the least solutions of certain systems of equations. They generate the same sets of graphs as the NLC-like vertex-rewriting C-edNCE graph grammars that are also context-free.

Actor grammars are a model of actor systems based on graph rewriting. Computation graphs model rewriting processes in actor grammars, and hence, computations in actor systems. It is shown that a structured transformation, as introduced in Janssens and Rozenberg (in “Graph Grammars and Their Application to Computer Science,” Lect. Notes in Comput. Sci., Vol. 291, pp. 280–298, Springer-Verlag, Berlin, 1987), may be viewed as a description of the external effect of a computation described by a computation graph. The use of computation graphs in investigating and comparing actor grammars is demonstrated by proving that actor grammars where, in each configuration, each message has a destination, are equivalent (in a well-defined sense) to arbitrary actor grammars.

Context-free hypergraph grammars and attribute grammars generate the same class of term languages. Extending the context-free hypergraph grammar with a context-free grammar and a semantic domain, a syntax-directed translation device is obtained that is equivalent to the attribute grammar.

Most NLC-like graph grammars generate node-labeled graphs. As one of the exceptions, eNCE graph grammars generate graphs with edge labels as well. We investigate this type of graph grammar and show that the use of edge labels (together with the NCE feature) is responsible for some new properties. Especially boundary eNCE (B-eNCE) grammars are considered. First, although eNCE grammars have the context-sensitive feature of “blocking edges,” we show that B-eNCE grammars do not. Second, we show the existence of a Chomsky normal form and a Greibach normal form for B-eNCE grammars. Third, the boundary eNCE languages are characterized in terms of regular tree and string languages. Fourth, we prove that the class of (boundary) eNCE languages properly contains the closure of the class of (boundary) NLC languages under node relabelings. Analogous results are shown for linear eNCE grammars.

A practical method is presented for extending the lookahead of LR parsers, by the addition of “reduce-arcs.” Applied to an LR(0) parser, this gives a machine which is close in size to the corresponding LALR(1) machine, but is capable of making use of unbounded lookahead. The class of grammars parsable by this method is a subset of the LR-regular grammars which is shown to be properly included in the LALR( k ) grammars, if limited to k symbols of lookahead, but also includes non-LR grammars if no such limit is imposed. Application is foreseen to error recovery in LALR(1) parsers, as well as the handling of occasional non-LALR(1) situations in normal parsing.

An attribute grammar is simple multi-visit if each attribute of a nonterminal has a fixed visit-number associated with it such that, during attribute evaluation, the attributes of a node which have visit-number j are computed at the jth visit to the node. An attribute grammar is l-ordered if for each nonterminal a linear order of its attributes exists such that the attributes of a node can always be evaluated in that order (cf. the work of Kastens).An attribute grammar is simple multi-visit if and only if it is l-ordered. Every noncircular attribute grammar can be transformed into an equivalent simple multi-visit attribute grammar which uses the same semantic operations.For a given distribution of visit-numbers over the attributes, it can be decided in polynomial time whether the attributes can be evaluated according to these visit-numbers. The problem whether an attribute grammar is simple multi-visit is NP-complete.

The equivalence problem for context-free grammars is “given two arbitrary grammars, do they generate the same language?” Since this is undecidable in general attention has been restricted to decidable subclasses of the context-free grammars. For example, the classes of LL(k) grammars and real-time strict deterministic grammars. In this paper it is shown that the equivalence problem for LL-regular grammars is decidable by reducing it to the equivalence problem for real-time strict deterministic grammars. Moreover, we show that the LL-regular equivalence problem is a special case of a more general equivalence problem which is also decidable. Our techniques can also be used to show that the equivalence problem for LR-regular grammars is decidable if and only if the equivalence problem for LR(0) grammars is decidable.

Formal grammars and formal languages are studied from the viewpoint of time-bounded grammars. A time-bound on a grammar is a measure of the “derivational complexity” of the language generated. Based on results of Gladkii [7] on connectivity in grammars, it is shown that a “linear speedup” can be obtained and that one can construct Turing acceptors to simulate grammars without loss of time. Positive containment and closure properties are also studied.

The recognizable sets of value trees (pseudoterms) are shown to be exactly projections of sets of derivation trees of (extended) context-free grammars.

This paper is concerned with the class of web grammars introduced by Pfaltz Rosenfeld and Montanari. In this paper, we show that context-sensitive web grammar cannot erase arcs, and monotone context-sensitive web grammar can erase arcs but cannot erase any vertices and they satisfy the condition |@a|@?|@b| in the rules @a@?@b. Then some hierarchical results hold, when grammars are normal and nonnormal. Normal grammars have rules that each vertex to be rewritten has exactly one image in the right member of the rule; nonnormal ones have rules that some vertices have two more images. Also, it is shown that there exists a complete grammar which generates some types of Eulerian graphs, line graphs and 3-connected graphs.

We give a number of algorithms which for a finite set of finite sequences of strings of symbols decide whether or not there exists a grammar of a certain fixed type such that each of the sequences is a derivation (or subderivation) by the grammar. Whenever such grammars exist, our algorithms will effectively produce one of them. The types of grammars which we consider operate by applying rules in parallel to all symbols in the strings; thus they are similar to other parallel type grammars which have been actively investigated in recent years. We restrict our attention to the types of grammars which have been found useful in modeling developmental processes in biology. In view of this, our algorithms can be considered to produce, from a finite number of observations of the development of a particular kind of organism, a model which represents the developmental rules of that organism. We discuss the relevance of our results to formal language theory and to developmental biology.

Regular grammars with attributes overcome some limitations of classical regular grammars, sensibly enhancing their expressiveness. However, the addition of attributes increases the complexity of this formalism leading to intractability in the general case. In this paper, we consider regular grammars with attributes ranging over integers, providing an in-depth complexity analysis. We identify relevant fragments of tractable attribute grammars, where complexity and expressiveness are well balanced. In particular, we study the complexity of the classical problem of deciding whether a string belongs to the language generated by any attribute grammar from a given class C (call it parse"["C"]). We consider deterministic and ambiguous regular grammars, attributes specified by arithmetic expressions over {||,+,-,@?,%,@?}, and a possible restriction on the attributes composition (that we call strict composition). Deterministic regular grammars with attributes computed by arithmetic expressions over {||,+,-,@?,%} are P-complete. If the way to compose expressions is strict, they can be parsed in L, and they remain tractable even if multiplication is allowed. Problem parse"["C"] becomes NP-complete for general regular grammars over {||,+,-,@?,%,@?} with strict composition and for grammars over {||,+,-,@?,%} with unrestricted attribute composition. Finally, we show that even in the most general case the problem is in polynomial space.

Document specification languages, like for instance XML, model documents using extended context-free grammars. These differ from standard context-free grammars in that they allow arbitrary regular expressions on the right-hand side of productions. To query such documents, we introduce a new form of attribute grammars (extended AGs) that work directly over extended context-free grammars rather than over standard context-free grammars. Viewed as a query language, extended AGs are particularly relevant as they can take into account the inherent order of the children of a node in a document. We show that non-circularity remains decidable in EXPTIME and establish the complexity of the non-emptiness and equivalence problem of extended AGs to be complete for EXPTIME. As an application we show that the Region Algebra expressions can be efficiently translated into extended AGs. This translation drastically improves the known upper bound on the complexity of the emptiness and equivalence test for Region Algebra expressions from non-elementary to EXPTIME. Finally, we characterize the expressiveness of extended AGs in terms of monadic second-order logic.

A generalization of ET0L systems is introduced: grammars with branching synchronization and nested tables. The main result is that branching synchronization grammars with tables of nesting depth n have the same string- and tree-generating power as n-fold compositions of top-down tree transducers. Based on this it is shown, e.g., that the family of generated string languages is a full principal AFL for each n.

Variations of programmed grammars, where control is imposed over sets of productions rather than over single productions, are studied. This corresponds to the notion of tables in the theory of L systems. The two variations of graph controduced correspond to programmed grammars with empty failure fields and those with unconditional transfer. Also some results concerning programmed grammars in their traditional form are obtained.

Translation between string and graph representations of programs and data may be formally defined by means of pair grammars. A pair grammar is composed of a pair of grammars whose rules and nonterminals are paired. The pair grammar defines a correspondence between elements of the languages defined by the two grammars. This correspondence may be viewed as a definition of the translation of the elements of one language into the elements of the other. Of particular interest is the case in which the first language is a set of strings and the second is a set of directed graphs with labeled arcs and nodes. Preliminary to the definition of pair grammars, a class of graph grammars are defined which are a generalization of ordinary context-free grammars. A graph grammar defines a language composed of a set of directed graphs. Pair grammars are constructed from pairs of graph grammars. Each unambiguous pair grammar defines a reversible function mapping one graph language onto another. Special cases of interest include string-to-graph, graph-to-string, and string-to-string mappings. In the general case a pair grammar defines a transformation on a set of graphs. Two extensions to the elementary pair grammars allow representation of hierarchies of graphs and constructs such as labels and go to statements. Examples are given of the translation of a major subset of Algol into flowchart graphs and the translation of Lisp S-expressions into list structure graphs with structured atoms.

LR-regular grammars are defined similarly to Knuth's LR(k) grammars, with the following exception: arbitrarily long look-ahead is allowed before making a parsing decision during the bottom-up syntactical analysis; however, this look-ahead is restricted in that the essential ''look-ahead information'' can be represented by a finite number of regular sets, thus can be computed by a finite state machine. LR-regular grammars can be parsed deterministically in linear time by a rather simple two-scan algorithm. Efficient parsers are constructed for given LR-regular grammars. The family of LR-regular languages is studied; it properly includes the family of deterministic CF languages and has similar properties. Necessary and sufficient conditions for a grammar to be LR-regular are derived and then utilized for developing parser generation techniques for arbitrary grammars.