Recording the use of memory in right-boundary grammars and push-down automata

Summary Within the framework of coordinated pair systems a push-down automaton A is formalized as an ordered pair (G ₁, G ₂) of grammars, where G ₁ is a right-linear grammar modelling the finite state control of A and the reading of the input of A, and G ₂ is a right-boundary grammar modelling the push-down store of A. In this paper we present a systematic investigation into the use of memory of right-boundary grammars. Various methods of recording the use of memory are introduced. The results presented concern regularity properties of each of the methods and the interrelationships of the records obtained by different methods. Finally the translation of these results to the level of push-down automata (coordinated pair systems) is discussed.     

Unification Grammars and Off-Line Parsability

Unification grammars are known to be Turing-equivalent; given a grammar G and a word w, it is undecidable whether w L(G). In order to ensure decidability, several constraints on grammars, commonly known as off-line parsability (OLP), were suggested, such that the recognition problem is decidable for grammars which satisfy OLP. An open question is whether it is decidable if a given grammar satisfies OLP. In this paper we investigate various definitions of OLP and discuss their interrelations, proving that some of the OLP variants are indeed undecidable. We then present a novel, decidable OLP constraint which is more liberal than the existing decidable ones.     

On grammar forms with terminal context

Summary A context-free grammar form G defines a family of context-free grammars {ie397-01}(G). In this paper {ie397-02}(G) is extended to give the family of terminal context grammars {ie397-03}(G), which were introduced by Book [4]. It is shown that the families of languages defined by {ie397-04}(G) and {ie397-05}(G) are equal when G is an -free context-free grammar form. This generalizes the result of Book [4] for context-free grammars and underlines the usefulness of the notion of grammar forms in formal language theory.The work of the second author was carried out partially under a National Research Council of Canada Grant. No. A-7700 and partially under the auspices of the University of Karlsruhe     

Control sets on grammars using depth-first derivations

Control sets on grammars are extended to depth-first derivations. It is proved that a context-free language is generated by the depth-first derivations of an arbitrary context-free grammar controlled by an arbitrary regular set. This result is sharpened to obtain a new characterization of the family of derivation-bounded languages: a languageL is derivation bounded if and only if it is generated by the depth-first derivations of a context-free grammarG controlled by a regular subsetR of the Szilard language ofG. The left-derivation-bounded languages are characterized analogously using leftmost derivations. It is proved that a grammarG is nonterminal bounded if and only if the Szilard language defined using only the depth-first derivations ofG is regular. Finally, it is proved that if a family of languagesC is a trio, a semi-AFL, an AFL, or an AFL closed under -free substitution, then the family of languages generated using arbitrary context-free grammars controlled by members ofC is full, is closed under reversal, and has the closure properties assumed ofC.     

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.     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

k-visit attribute grammars

It is shown that any well-defined attribute grammar isk-visit for somek. Furthermore it is shown that given a well-defined grammarG and an integerk, it is decidable whetherG isk-visit. Finally we show that thek-visit grammars specify a proper hierarchy with respect to translations.     

Controlability by completions of partial upper triangular matrices

Given an irreducible partial upper triangularn × n matrixA, it is shown that for every nonzero vectorb there exists a completionA _c ofA such that the pair (A _c ,b) is controllable. Various extensions and applications of this result are given.Partially supported by NSF Grant DMS-9000839 and by the United States-Israel Binational Fund.     

Controllability of right invariant systems on real simple Lie groups of typeF 4,G 2,C n,andB n *

We deal with controllability of right-invariant systems for some real simple Lie groups ofF ₄,G ₂,C _n , andB _n types. We prove that the so-calledcontrollability rank condition is a necessary and sufficient condition for controllability for an open class of systems. In other papers, analogous results were obtained for Lie groups of the remaining types (i.e.,E ₆,E ₇,E ₈,A _n , andD _n ) using a special property of the root systems of their Lie algebras.     

Parallel communicating grammar systems with terminal transmission

We introduce a new variant of PC grammar systems, called PC grammar systems with terminal transmission, PCGSTT for short. We show that right-linear centralized PCGSTT have nice formal language theoretic properties: they are closed under gsm mappings (in particular, under intersection with regular sets and under homomorphisms) and union; a slight variant is, in addition, closed under concatenation and star; their power lies between that of n-parallel grammars introduced by Wood and that of matrix languages of index n, and their relation to equal matrix grammars of degree n is discussed. We show that membership for these language classes is complete for NL. In a second part of the paper, we discuss questions concerning grammatical inference of these systems. More precisely, we show that PCGSTT whose component grammars are terminal distinguishable right-linear, a notion introduced by Radhakrishnan and Nagaraja in [33,34], are identifiable in the limit if certain data communication information is supplied in addition.     

The Grammar Deployment Kit — System Demonstration —

Grammar deployment is the process of turning a given grammar specification into a working parser. The Grammar Deployment Kit (for short, GDK) provides tool support in this process based on grammar engineering methods. We are mainly interested in the deployment of grammars for software renovation tools, that is, tools for software re- and reverse engineering. The current version of GDK is optimized for Cobol. We assume that grammar deployment starts from an initial grammar specification which is maybe still ambiguous or even incomplete. In practice, grammar deployment binds unaffordable human resources because of the unavailability of suitable grammar specifications, the diversity of parsing technology as well as the limitations of the technology, integration problems regarding the development of software renovation functionality, and the lack of tools and adherence to firm methods for grammar engineering. GDK helps to largely automate grammar deployment because tool support for grammar adaptation and parser generation is provided. We support different parsing technologies, among them btyacc, that is, yacc with backtracking. GDK is free software.     

An algebraic technique for context-sensitive parsing

A technique that represents derivations of a context-free grammarG over a semiring and that obtains for a wordw inL(G) the set of all canonical parses forw has previously been described. A state grammar is one of a collection of grammars that place restrictions on the manner of application of context-free-like productions and that generate a noncontext-free language. The context-free properties of a state grammar have been used to extend the algebraic parsing technique for languages generated by state grammars,viz., context-sensitive languages. The extension for state grammars is not unlike that required for other types of grammars in whose collection state grammars are representative.     

On the endomorphisms of finite automata

The properties of endomorphisms and automorphisms of a finite, deterministic automatonA related to the smallest input-independent partition on the set of internal states ofA are investigated. The setH ^d of all thed-endomorphisms ofA defined here, as well as the setG ^d of all thed-automorphisms ofA, are studied in detail. It is proved thatH ^d forms a polyadic semigroup, whileG ^d forms a polyadic group. Connections betweenG ^d and the groupG(A) of all the automorphisms ofA are examined. The upper bound for the cardinality ofG ^d is given.Finally, by means of the theory ofd-automorphisms, some problems of the theory of strictly periodic automata are solved; in the first place, the necessary and sufficient condition for the reducibility of an arbitrary strictly periodic automation is given.     

Parameter-reduction of higher level grammars

A higher level (OI-) grammar is called terminating if for every accessible term t there is at least one terminal term which can be derived from t. A grammar is called parameter-reduced if it is terminating and has no superfluous parameters. For every grammar G of level n0 which generates at least one term we construct grammars R(G) and P(G) such that R(G) and P(G) generate the same language as G but are terminating and parameter-reduced respectively. We introduce a hierarchy of restrictions to the delection capability of the grammars which allow a gradual decrease in the complexity of the algorithms from n-iterated exponential time to polynomial time.     

Coloring inductive graphs on-line

In this paper we consider the problem of on-line graph coloring. In an instance of on-line graph coloring, the nodes are presented one at a time. As each node is presented, its edges to previously presented nodes are also given. Each node must be assigned a color, different from the colors of its neighbors, before the next node is given. LetA(G) be the number of colors used by algorithmA on a graphG and letx(G) be the chromatic number ofG. The performance ratio of an on-line graph coloring algorithm for a class of graphsC is max_{G C(A(G)/(G))}. We consider the class ofd-inductive graphs. A graphG isd-inductive if the nodes ofG can be numbered so that each node has at mostd edges to higher-numbered nodes. In particular, planar graphs are 5-inductive, and chordal graphs arex(G)-inductive. First Fit is the algorithm that assigns each node the lowest-numbered color possible. We show that ifG isd-inductive, then First Fit usesO(d logn) colors onG. This yields an upper bound ofo(logn) on the performance ratio of First Fit on chordal and planar graphs. First Fit does as well as any on-line algorithm ford-inductive graphs: we show that, for anyd and any on-line graph coloring algorithmA, there is ad-inductive graph that forcesA to use (d logn) colors to colorG. We also examine on-line graph coloring with lookahead. An algorithm is on-line with lookaheadl, if it must color nodei after examining only the firstl+i nodes. We show that, forl/logn, the lower bound ofd logn colors still holds.This research was supported by an IBM Graduate Fellowship.     

Existence and efficient construction of fast Fourier transforms on supersolvable groups

The linear complexityL _K(A) of a matrixA over a fieldK is defined as the minimal number of additions, subtractions and scalar multiplications sufficient to evaluateA at a generic input vector. IfG is a finite group andK a field containing a primitive exp(G)-th root of unity,L _K(G):= min{L _K(A)|A a Fourier transform forKG} is called theK-linear complexity ofG. We show that every supersolvable groupG has amonomial Fourier Transform adapted to a chief series ofG. The proof is constructive and gives rise to an efficient algorithm with running timeO(|G|²log|G|). Moreover, we prove that these Fourier transforms are efficient to evaluate:L _K(G)8.5|G|log|G| for any supersolvable groupG andL _K(G)1.5|G|log|G| for any 2-groupG.     

Meta-modelling and graph grammars for multi-paradigm modelling in AToM<Superscript>3</Superscript>

This paper presents the combined use of meta-modelling and graph grammars for the generation of visual modelling tools for simulation formalisms. In meta-modelling, formalisms are described at a meta-level. This information is used by a meta-model processor to generate modelling tools for the described formalisms. We combine meta-modelling with graph grammars to extend the model manipulation capabilities of the generated modelling tools: edit, simulate, transform into another formalism, optimize and generate code. We store all (meta-)models as graphs, and thus, express model manipulations as graph grammars.We present the design and implementation of these concepts in AToM³ (A_To_ol for M_ulti-formalism, M_eta-M_odelling). AToM³ supports modelling of complex systems using different formalisms, all meta-modelled in their own right. Models in different formalisms may be transformed into a single common formalism for further processing. These transformations are specified by graph grammars. Mosterman and Vangheluwe [18] introduced the term multi-paradigm modelling to denote the combination of multiple formalisms, multiple abstraction levels, and meta-modelling. As an example of multi-paradigm modelling we present a meta-model for the Object-Oriented Continuous Simulation Language OOCSMP, in which we combine ideas from UML class diagrams (to express the OOCSMP model structure), Causal Block Diagrams (CBDs), and Statecharts (to specify the methods of the OOCSMP classes). A graph grammar is able to generate OOCSMP code, and then a compiler for this language (C-OOL) generates Java applets for the simulation execution.     

On the equivalence and containment problems for context-free languages

LetG andG ₀ be context-free grammars. Necessary and sufficient conditions onG ₀ are obtained for the decidability ofL(G ₀) L((G) It is also shown that it is undecidable for whichG ₀,L(G) is decidable. Furthermore, given thatL(G) is decidable for a fixedG ₀, there is no effective procedure to determine the algorithm which decidesL(G) IfL(G ₀) is a regular set,L(G) = L(G ₀) is decidable if and only ifL(G ₀) is bounded. However, there exist non-regular, unboundedL(G ₀) for whichL(G) = L(G ₀) is decidable.     

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.