LL(k)-PARSING OF COUPLED-CONTEXT-FREE GRAMMARS

Coupled-context-free grammars are a natural generalization of context-free grammars obtained by combining nonterminals to corresponding parentheses which can only be substituted simultaneously. Refering to the generative capacity of the grammars we obtain an infinite hierarchy of languages that comprises the context-free languages as the first and all the languages generated by TAGs as the second element. Here, we present a generalization of the context-free LL(k) -notion onto coupled-context-free grammars, which leads to a characterization of subclasses of coupled-context-free grammars–and in this way of TAGs as well–which can be parsed in linear time. The parsing procedure described works incrementally so that it can be used for on-line parsing of natural language. Examples show that important elements of the tree-adjoining languages can be generated by LL(k )-coupled-context-free grammars.     

Building Construction Sets by Tiling Grammar Simplification

This paper poses the problem of fabricating physical construction sets from example geometry: A construction set provides a small number of different types of building blocks from which the example model as well as many similar variants can be reassembled. This process is formalized by tiling grammars. Our core contribution is an approach for simplifying tiling grammars such that we obtain physically manufacturable building blocks of controllable granularity while retaining variability, i.e., the ability to construct many different, related shapes. Simplification is performed by sequences of two types of elementary Operations: non‐local joint edge collapses in the tile graphs reduce the granularity of the decomposition and approximate replacement Operations reduce redundancy. We evaluate our method on abstract graph grammars in addition to computing several physical construction sets, which are manufactured using a commodity 3D printer.     

On the generative capacity of compound string and array grammars

The operation of composition is a device introduced by Abraham [1] to increase the generative capacity of regular matrix grammars. But not all families of grammars have their generative capacity increased by this operation. P?un [5] has proved that composition increases the generative capacity of linear grammars but not of regular, CF, CS or PS grammars. In this note, we show that the generative power of k-linear (k ? 1) grammars is increased by composition. In fact, it is of interest to note that the families of compound linear and compound k-linear languages are equal. Furthermore, the family of compound linear languages is an AFL, properly contained in the family of CFLs. Certain other families of string and array grammars whose generative capacities are increased by the operation of composition are also provided.     

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     

Activatable tiles for compact robust programmable molecular assembly and other applications

Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors. Since 2003 there have been several designs of error-resilient tile sets but all of these existing error-resilient tile systems assumed directional growth of the tiling assembly. This is a very strong assumption because experiments show that tile self-assembly does not necessarily behave in such a fashion, since they may also grow in the reverse of the intended direction. The assumption of directional growth of the tiling assembly also underlies the growth model in theoretical assembly models such as the TAM. What is needed is a means for enforce this directionality constraint, which will allow us to reduce assembly errors. In this paper we describe a protection/deprotection strategy to strictly enforce the direction of tiling assembly growth so that the assembly process is robust against errors. Initially, we start with (1) a single “activated” tile with output pads that can bind with other tiles, along with (2) a set of “deactivated” tiles, meaning that the tile’s output pads are protected and cannot bind with other tiles. After other tiles bind to a “deactivated” tile’s input pads, the tile transitions to an active state and its output pads are exposed, allowing further growth. When these are activated in a desired order, we can enforce a directional assembly at the same scale as the original one. Such a system can be built with minimal modifications of existing DNA tile nanostructures. We propose a new type of tiles called activatable tiles and its role in compact proofreading. Activatable tiles can be thought of as a particular case of the more recent signal tile assembly model, where signals transmit binding/unbinding instructions across tiles on binding to one or more input sites. We describe abstract and kinetic models of activatable tile assembly and show that the error rate can be decreased significantly with respect to Winfree’s original kinetic tile assembly model without considerable decrease in assembly growth speed. We prove that an activatable tile set is an instance of a compact, error-resilient and self-healing tile-set. We describe a DNA design of activatable tiles and a mechanism of deprotection using DNA polymerization and strand displacement. We also perform detailed stepwise simulations using a DNA Tile simulator Xgrow, and show that the activatable tiles mechanism can reduce error rates in self assembly. We conclude with a brief discussion on some applications of activatable tiles beyond computational tiling, both as (1) a novel system for concentration of molecules, and (2) a catalyst in sequentially triggered chemical reactions.     

Tile rewriting grammars and picture languages

Tile rewriting grammars (TRG) are a new model for defining picture languages. A rewriting rule changes a homogeneous rectangular subpicture into an isometric one tiled with specified tiles. Derivation and language generation with TRG rules are similar to context-free grammars. A normal form and some closure properties are presented. We prove this model has greater generative capacity than the tiling systems of Giammarresi and Restivo and the grammars of Matz, another generalization of context-free string grammars to 2D. Examples are shown for pictures made by nested frames and spirals.     

Fixed-point tile sets and their applications

An aperiodic tile set was first constructed by R. Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many fields, ranging from logic (the Entscheidungsproblem) to physics (quasicrystals). We present a new construction of an aperiodic tile set that is based on Kleene?s fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann?s self-reproducing automata; similar ideas were also used by P. Gács in the context of error-correcting computations. This construction is rather flexible, so it can be used in many ways. We show how it can be used to implement substitution rules, to construct strongly aperiodic tile sets (in which any tiling is far from any periodic tiling), to give a new proof for the undecidability of the domino problem and related results, to characterize effectively closed one-dimensional subshifts in terms of two-dimensional subshifts of finite type (an improvement of a result by M. Hochman), to construct a tile set that has only complex tilings, and to construct a “robust” aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. For the latter, we develop a hierarchical classification of points in random sets into islands of different ranks. Finally, we combine and modify our tools to prove our main result: There exists a tile set such that all tilings have high Kolmogorov complexity even if (sparse enough) tiling errors are allowed. Some of these results were included in the DLT extended abstract (Durand et al., 2008 [9]) and in the ICALP extended abstract (Durand et al., 2009 [10]).     

A computational model for tiling recognizable two-dimensional languages

Tiling systems are a well accepted model to define recognizable two-dimensional languages but they are not an effective device for recognition unless a scanning strategy for the pictures is fixed. We define a tiling automaton as a tiling system equipped with a scanning strategy and a suitable data structure. The class of languages accepted by tiling automata coincides with the REC family. In this framework it is possible to define determinism, non-determinism and unambiguity. Then (deterministic) tiling automata are compared with the other known (deterministic) automata models for two-dimensional languages.     

On some families of languages related to developmental systems

OL systems and TOL systems are the simplest mathematical models for the study of the development of biological organisms with or without a variable environment, respectively. This paper contributes to the study of the properties of the languages generated by these systems and by their generalizations. Macro OL (TOL) languages are languages obtained by substituting languages of a given type in OL (TOL) languages. We study properties of certain families of macro OL (TOL) languages in particular we show that they are full AFL's.

We observe that OL, TOL systems and many of their generalizations can be viewed as special classes of index grammars.     

Tree controlled grammars

Languages are studied which can be generated by context-free grammars under a single simple restriction which must be satisfied by its derivation trees. Using tree controlled grammars (TC grammars for short) all unambigous and some inherently ambigous context-free languages, and also some non context-free languages can be parsed in timeO(n ²). The classes of regular, linear, context-free, EOL, ETOL and type 0 languages can be characterized in a natural manner using TC grammars. A context-free generator for all type 0 languages is exhibited. Some normal forms for TC grammars are established but it is shown that many common normal forms (e. g. Greibach normal form) cannot be obtained for TC grammars in general.     

On the structure of context-sensitive grammars

It is well known that the family of context-sensitive grammars generate languages which are not context-free and that it is undecidable whether a context-sensitive grammar generates a context-free language. However, the mechanism by which the use of context allows a non-context-free language to be generated is not well understood. In this paper we attempt to focus on this problem by surveying some of the results which speak to two questions: (i) What constraints can be placed on the form of the rules of context-sensitive grammars without restricting the weak generative capacity? (ii) What (nontrivial) constraints can be placed on the form of the rules of context-sensitive grammars such that only context-free languages will be generated?     

Unrestricted gapping grammars1

Since Colmerauer's introduction of metamorphosis grammars (MGs), with their associated type-O-like grammar rules, there has been a desire to allow more general rule formats in logic grammars. Gap symbols were added to the MG rule by Pereira, resulting in extraposition grammars (XGs). Gaps, which are referenced by gap symbols, are sequences of zero or more unspecified symbols which may be present anywhere in a sentence or in a sentential form. However, XGs imposed restrictions on the position of gap symbols and on the contents of gaps. With the introduction of gapping grammars (GGs) by Dahl, these restrictions were removed but the rule was still required to possess a nonterminal symbol as the first symbol on the left-hand side. This restriction is removed with the introduction of unrestricted gapping grammars. FIGG, a flexible implementation of gapping grammars, possesses a bottom-up parser which can process a large subset of unrestricted gapping grammars. It can be used to examine the usefulness of unrestricted GGs for describing phenomena of natural languages such as free word order and partially free word/constituent order. Unrestricted gapping grammars, as implemented in FIGG, can also be used to describe grammars (or metagrammars) that utilize the gap concept, such as Gazdar's generalized phrase structure grammars.     

上下文相关图文法的表达能力分析

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.     

A note on Lindenmayer systems,Szilard languages,spectra, and equivalence

We investigate the Szilard languages and the spectra of Lindenmayer systems through the generalization of Lindenmayer systems toK-iteration grammars and context-sensitiveK-iteration grammars. Various decidability and undecidability results are presented with respect to the evaluation of Szilard languages and spectra for particularK-iteration grammars. Further, two different definitions of the Szilard and spectral equivalence of twoK-iteration grammars are investigated.Work carried out under a National Research Council of Canada Grant No. A-7700.     

L-fuzzy grammars

An L-fuzzy grammar is defined by assigning the element of lattice to the rewriting rules of a formal grammar. According to the kind of lattice, say, distributive lattice, lattice-ordered group, and lattice-ordered monoid, two type of L-fuzzy grammars are defined. It is shown that some context-sensitive languages can be generated by type 3 $\text{1-L-}\text{fuzzy}$ grammars with cut points. It is also shown that for type 2 L-fuzzy grammars, Chomsky and Greibach normal form can be constructed as an extension of corresponding notion in the theory of formal grammars.     

The complexity of the membership problem for some extensions of context-free languagest†

The time and tape complexity of some families of languages defined in the literature by altering methods of generation by context-free grammars is considered. Specifically; it is shown that the following families of languages can be recognized by deterministic multitape Turing machines either in polynomial time or within (log n)² tape:

1) the context independent developmental (EOL) languages;

2) the simple matrix languages;

3) the languages generated by derivation restricted state grammars.:

4) the languages generated by linear context-free grammars with certain non-regular control sets;

5) the languages generated by certain classes of vector grammars.

In fact, these languages are of the same tape complexity as context-free languages. Other results indicate the complexity of EDOL languages and the effects on complexity of applying the homomorphic replication operator to regular and context-free languages.     

THE COMPUTATIONAL COMPLEXITY OF THE UNIVERSAL RECOGNITION PROBLEM FOR PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS

A number of grammatical formalisms have been proposed to describe the syntax of natural languages, and the universal recognition problems for some of those classes of grammars have been studied. A universal recognition problem for a class Q of grammars is the one to decide, taking a grammar G ∈ G and a string ui as an input, whether G can generate w or not. In this paper, the computational complexities of the universal recognition problems for parallel multiple context-free grammars, multiple context-free grammars, and their subclasses are discussed.     

On LLP(k) grammars and languages

The paper studies the family of LLP(k) grammars introduced by Lomet. Two new grammatical characterizations for this class are presented. The first one shows that these grammars form an extension of strict deterministic grammars, in particular, any strict deterministic grammar is an LLP(0) one. LLP(k) grammars share with this subclass many important mathematical properties. The second characterization proves LLP(k) grammars to be a natural cross between LL(k) and LR(k) grammars. Relationships between corresponding families of languages are also investigated.