A normal form theorem for label grammars

We characterize the images of Szilard languages under decreasing homomorphisms using so-called label grammars and show that each -free label language is in fact the coding of some Szilard language. This result shows that decreasing homomorphisms do not have more generating power on Szilard languages than codings, except that they generate the empty word. Label grammars naturally define a subclass of labelled Petri nets for which, unlike in the general case, it is now possible to eliminate -labelled transitions.     

LR-parsing of extended context free grammars

Summary To improve the readability of a grammar it is common to use extended context free grammars (ECFGs) which are context free grammars (CFGs) extended with the repetition operator (^*), the alternation operator (¦) and parentheses to express the right hand sides of the productions. The topic treated here is LR-parsing of ECFGs. The LR(k) concept is generalized to ECFGs, a set of LR-preserving transformations from ECFGs to CFGs is given and finally it is shown how to construct LR-parsers directly from ECFGs.     

Evolutionary induction of stochastic context free grammars

This paper describes an evolutionary approach to the problem of inferring stochastic context-free grammars from finite language samples. The approach employs a distributed, steady-state genetic algorithm, with a fitness function incorporating a prior over the space of possible grammars. Our choice of prior is designed to bias learning towards structurally simpler grammars. Solutions to the inference problem are evolved by optimizing the parameters of a covering grammar for a given language sample. Full details are given of our genetic algorithm (GA) and of our fitness function for grammars. We present the results of a number of experiments in learning grammars for a range of formal languages. Finally we compare the grammars induced using the GA-based approach with those found using the inside-outside algorithm. We find that our approach learns grammars that are both compact and fit the corpus data well.     

Learning deterministic context free grammars: The Omphalos competition

This paper describes the winning entry to the Omphalos context free grammar learning competition. We describe a context-free grammatical inference algorithm operating on positive data only, which integrates an information theoretic constituent likelihood measure together with more traditional heuristics based on substitutability and frequency. The competition is discussed from the perspective of a competitor. We discuss a class of deterministic grammars, the Non-terminally Separated (NTS) grammars, that have a property relied on by our algorithm, and consider the possibilities of extending the algorithm to larger classes of languages. Editor: Georgios Paliouras and Yasubumi Sakakibara     

Incremental learning of context free grammars based on bottom-up parsing and search

This paper describes approaches for machine learning of context free grammars (CFGs) from positive and negative sample strings, which are implemented in Synapse system. The grammatical inference consists of a rule generation by “inductive CYK algorithm,” mechanisms for incremental learning, and search. Inductive CYK algorithm generates minimum production rules required for parsing positive samples, when the bottom-up parsing by CYK algorithm does not succeed. The incremental learning is used not only for synthesizing grammars by giving the system positive strings in the order of their length but also for learning grammars from other similar grammars. Synapse can synthesize fundamental ambiguous and unambiguous CFGs including nontrivial grammars such as the set of strings not of the form ww with w∈{a,b}⁺.     

Syntactic complexity of scattered context grammars

The syntactic complexity of scattered context grammars with respect to the number of nonterminals is investigated. First, the family of the recursively enumerable languages is characterized by some basic operations, such as quotient and coding, over the languages generated by propagating scattered context grammars with four nonterminals. Then, a new method of achieving the characterization of the family of recursively enumerable languages by scattered context grammars is given; in fact, this family is characterized by scattered context grammars with only five nonterminals and a single erasing production. Finally, it is demonstrated that the number of nonterminals can be decreased by one in the present characterizations if scattered context grammars start their derivations from a word rather than a single symbol.     

A method for transforming grammars into LL(k) form

Summary A new method for transforming grammars into equivalent LL(k) grammars is studied. The applicability of the transformation is characterized by defining a subclass of LR(k) grammars, called predictive LR(k) grammars, with the property that a grammar is predictive LR(k) if and only if the corresponding transformed grammar is LL(k). Furthermore, it is shown that deterministic bottom-up parsing of a predictive LR(k) grammar can be done by the LL(k) parser of the transformed grammar. This parsing method is possible since the transformed grammar always left-to-right covers the original grammar. The class of predictive LR(k) grammars strictly includes the class of LC(k) grammars (the grammars that can be parsed deterministically in the left-corner manner). Thus our transformation is more powerful than the one previously available, which transforms LC(k) grammars into LL(k) form.     

Nonterminal complexity of one-sided random context grammars

In the present paper, we study the nonterminal complexity of one-sided random context grammars. More specifically, we prove that every recursively enumerable language can be generated by a one-sided random context grammar with no more than ten nonterminals. An analogical result holds for thirteen nonterminals in terms of these grammars with the set of left random context rules coinciding with the set of right random context rules. Furthermore, we introduce the notion of a right random context nonterminal, defined as a nonterminal that appears on the left-hand side of a right random context rule. We demonstrate how to convert any one-sided random context grammar G to an equivalent one-sided random context grammar H with two right random context nonterminals. An analogical conversion is given in terms of (1) propagating one-sided random context grammars and (2) left random context nonterminals. In the conclusion, two open problems are stated.     

On the descriptional complexity of scattered context grammars

This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.     

A sampled normal form for feedback linearization

This paper discusses the problem of preserving approximated feedback linearization under digital control. Starting from a partially feedback linearizable affine continuous-time dynamics, a digital control procedure which maintains the dimension of the maximally feedback linearizable part up to any order of approximation with respect to the sampling period is proposed. The result is based on the introduction of a sampled normal form, a canonical structure which naturally appears when studying feedback linearization.This work was supported by an Italian 40% M.U.R.S.T. grant and a French M.E.N.-D.R.E.D. grant.