On permutative grammars generating context-free languages

A grammar is said to be permutative if it has permutation productions of the formAB BA in addition to context-free productions. Szilard languages and label languages are studied as examples of languages generable by permutative grammars. Particularly, sufficient conditions for a permutative grammar to generate a context-free language are studied.This work was supported by the Academy of Finland.     

A note on one-pass evaluation of attribute grammars

An attribute grammar is considered to be one-pass if all the attribute instances of any derivation tree can be evaluated by a process that traverses the tree from left to right visiting each subtree at most once. It is shown that this general class of one-pass grammars properly includesL-attributed grammars; in fact,L-attributed grammars can be viewed as a practical subset of the general class. General one-pass grammars can be evaluated using recursive procedures in the same way as forL-attributed grammars, provided that call-by-name parameters are available.     

Grammar functors and covers: From non-left-recursive to greibach normal form grammars

Attention is paid to structure preserving properties of transformations from a non-left-recursive context-free grammar to a Greibach normal form grammar. It is demonstrated that such a transformation cannot only be ambiguity preserving, but also both cover and functor relations between grammars or their associated syntax-categories can be obtained from such a transformation.     

Parallel permit grammars and some graph representations of Petri nets

The graph of a set grammar is introduced in such a way that each set rule of the grammar is represented by a cartesian subgraph of it. The correspondence between cartesian subgraphs and transitions of Petri nets (which satisfy the axiom of extensionality) is established. The set grammars with input (initial) and output (terminal) elements are studied in an analogy to Chomsky's string grammars and their strong equivalence. Permit rules and parallel permit rules are introduced in such a way that parallel permit grammars are more general tools than Petri nets themselves, because the equivalence between homogeneous parallel permit grammars and set grammars (and Petri nets) is proved.     

Colored operads,series on colored operads,and combinatorial generating systems

We introduce bud generating systems, which are used for combinatorial generation. They specify sets of various kinds of combinatorial objects, called languages. They can emulate context-free grammars, regular tree grammars, and synchronous grammars, allowing us to work with all these generating systems in a unified way. The theory of bud generating systems uses colored operads. Indeed, an object is generated by a bud generating system if it satisfies a certain equation in a colored operad. To compute the generating series of the languages of bud generating systems, we introduce formal power series on colored operads and several operations on these. Series on colored operads are crucial to express the languages specified by bud generating systems and allow us to enumerate combinatorial objects with respect to some statistics. Some examples of bud generating systems are constructed; in particular to specify some sorts of balanced trees and to obtain recursive formulas enumerating these.     

Decidability and density in two-symbol grammar forms

It is proved that form equivalence is decidable for context-free grammar forms with only one nonterminal and one terminal symbol. However it also proved that there are “many” grammatical families generated by such forms: with some trivial exceptions, the families are dense in the sense that between any two families one can “squeeze” in a third one. The results obtained are applied also to L forms.     

Some combinatorial arrays generated by context-free grammars

A context-free grammar G$G$ over an alphabet A$A$ is defined as a set of substitution rules that replace a letter in A$A$ by a formal function over A$A$. The purpose of this paper is to show that some combinatorial arrays, such as the Catalan’s triangle, can be generated by context-free grammars in three variables.     

A context-free grammar for the e-positivity of the trivariate second-order Eulerian polynomials

Ma-Ma-Yeh made a beautiful observation that a transformation of the grammar of Dumont instantly leads to the γ-positivity of the Eulerian polynomials. We notice that the transformed grammar bears a striking resemblance to the grammar for 0-1-2 increasing trees also due to Dumont. The appearance of the factor of two fits perfectly in a grammatical labeling of 0-1-2 increasing plane trees. Furthermore, the grammatical calculus is instrumental to the computation of the generating functions. This approach can be adapted to study the e-positivity of the trivariate second-order Eulerian polynomials first introduced by Dumont in the contexts of ternary trees and Stirling permutations, and independently defined by Janson, in connection with the joint distribution of the numbers of ascents, descents and plateaux over Stirling permutations.     

Attribute grammars and automatic complexity analysis

Attribute grammars provide a concise way to describe traits of a wide family of structures. Structures defined by context-free grammars have been well studied by Delest, Fédou, and more recently by Duchon. One of the principle benefits of this approach is the easy access to multivariate generating function equations from which average and higher moments are easily accessible. This work extends these notions to a wider class of structures and considers the application to algorithm analysis.     

Context-free pairs of groups II - Cuts, tree sets, and random walks

This is a continuation of the study, begun by Ceccherini-Silberstein and Woess (2009) [5], of context-free pairs of groups and the related context-free graphs in the sense of Muller and Schupp (1985) [22]. The graphs under consideration are Schreier graphs of a subgroup of some finitely generated group, and context-freeness relates to a tree-like structure of those graphs. Instead of the cones of Muller and Schupp (1985) [22] (connected components resulting from deletion of finite balls with respect to the graph metric), a more general approach to context-free graphs is proposed via tree sets consisting of cuts of the graph, and associated structure trees. The existence of tree sets with certain "good" properties is studied. With a tree set, a natural context-free grammar is associated. These investigations of the structure of context free pairs, resp. graphs are then applied to study random walk asymptotics via complex analysis. In particular, a complete proof of the local limit theorem for return probabilities on any virtually free group is given, as well as on Schreier graphs of a finitely generated subgoup of a free group. This extends, respectively completes, the significant work of Lalley (1993, 2001) [18,20].     

Pure 2D picture grammars and languages

A new syntactic model, called pure two-dimensional (2D) context-free grammar (P2DCFG), is introduced based on the notion of pure context-free string grammar. The rectangular picture generative power of this 2D grammar model is investigated. Certain closure properties are obtained. An analogue of this 2D grammar model called pure 2D hexagonal context-free grammar (P2DHCFG) is also considered to generate hexagonal picture arrays on triangular grids.     

Uncle-attributed grammars

Evaluation of inherited attributes is a problem in conjunction with LR parsing, because the derivation tree is incomplete during parsing. An evaluation scheme for inherited attributes is presented based on a restricted grammar class, uncle-attributed grammars. A transformation to the uncle-attributed form is described for L-attributed grammars.     

Non-associative Lambek Categorial Grammar in Polynomial Time

We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorial grammar to an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial time, this proves that a sentence generated by any non-associative Lambek categorial grammar can be recognized in polynomial time.     

The power of programmed grammars with graphs from various classes

Programmed grammars, one of the most important and well investigated classes of grammars with context-free rules and a mechanism controlling the application of the rules, can be described by graphs. We investigate whether or not the restriction to special classes of graphs restricts the generative power of programmed grammars with erasing rules and without appearance checking, too. We obtain that Eulerian, Hamiltonian, planar and bipartite graphs and regular graphs of degree at least three are pr-universal in that sense that any language which can be generated by programmed grammars (with erasing rules and without appearance checking) can be obtained by programmed grammars where the underlying graph belongs to the given special class of graphs, whereas complete graphs, regular graphs of degree 2 and backbone graphs lead to proper subfamilies of the family of programmed languages.     

最大乘积型Fuzzy上下无关文法与下推自动机

在文献[1]的基础上,讨论了最大乘积型Fuzzy上下文无关文法与最大乘积型Fuzzy下推自动机的关系,即:由给定的最大乘积型Fuzzy上下文无关文法可构造一个最大乘积型Fuzzy下推自动机使得二者接受的语言集相同,反之亦然。从而达到自动识别语言的目的。     

On context-free and Szilard languages

Szilard languages of context-free grammars are studied. Especially, classical pumping, generalized pumping, Sokolowski's criterion, and semilinearity are considered as possible distinguishing properties between context-free and Szilard languages.This work was supported by the Academy of Finland.     

A sentence generator for testing parsers

A fast algorithm is given to produce a small set of short sentences from a context free grammar such that each production of the grammar is used at least once. The sentences are useful for testing parsing programs and for debugging grammars (finding errors in a grammar which causes it to specify some language other than the one intended). Some experimental results from using the sentences to test some automatically generated simpleLR(1) parsers are also given.     

Growth and ergodicity of context-free languages

A language over a finite alphabet is called growth-sensitive if forbidding any set of subwords yields a sublanguage whose exponential growth rate is smaller than that of . It is shown that every ergodic unambiguous, nonlinear context-free language is growth-sensitive. ``Ergodic' means for a context-free grammar and language that its dependency di-graph is strongly connected. The same result as above holds for the larger class of essentially ergodic context-free languages, and if growth is considered with respect to the ambiguity degrees, then the assumption of unambiguity may be dropped. The methods combine a construction of grammars for -block languages with a generating function technique regarding systems of algebraic equations.

     

A formal approach to subgrammar extraction for NLP

The problem of subgrammar extraction is precisely defined in the following way: Given a grammar $G$ and a set of words $W$, find a smallest subgrammar of $G$ that accepts the same set of sentences from $W^1$ as $G$, and for each of them produces the same parse trees. In practical Natural Language Processing applications, the set of words $W$ is obtained from the text unit. There are practical motivations for doing this operation “just-in-time”, i.e. just before processing the text; hence it is required that this operation be done in an automatic and efficient way. After defining the problem in the general framework, we discuss the problem for context-free grammars (CFG), and give an efficient algorithm for it. We prove that finding the smallest subgrammar for HPSGs is an NP-hard problem, and give an efficient algorithm that solves an easier, approximate version of the problem. We also discuss how the algorithm can be efficiently implemented.