Tissue P systems with channel states

We consider tissue-like P systems with states associated with the links (we call them synapses) between cells, controlling the passage of objects across the links. We investigate the computing power of such devices for the case of using—in a sequential manner—antiport rules of small weights. Systems with two cells are proved to be universal when having arbitrarily many states and minimal antiport rules, or one state and antiport rules of weight two. Also the systems with arbitrarily many cells, three states, and minimal antiport rules are universal. In contrast, the systems with one cell and any number of states and rules of any weight only compute Parikh sets of matrix languages (generated by matrix grammars without appearance checking); characterizations of Parikh images of matrix languages are obtained for such one-cell systems with antiport rules of a reduced weight.     

A unifying approach to picture grammars

Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such grammars can be unified and extended using an approach, whereby the right part of a rule is formalized by means of a finite set of permitted tiles. We focus on a simple type of tiling, named regional, and define the corresponding regional tile grammars. They include both Siromoney?s (or Matz?s) Kolam grammars and their generalization by Pr?ša, as well as Drewes?s grid grammars. Regionally defined pictures can be recognized with polynomial-time complexity by an algorithm extending the CKY one for strings. Regional tile grammars and languages are strictly included into our previous tile grammars and languages, and are incomparable with Giammarresi-Restivo tiling systems (or Wang systems).     

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.     

Symmetric rules for translation of English and Chinese

A system of grammars using symmetric phrase structure and translation rules in a Lisp version of Prolog is shown to provide symmetric bidirectional translation between English and Chinese for a fragment of the two languages. It is argued that symmetric grammars and translation rules significantly reduce the total grammar writing requirement for translation systems, and that research on symmetric translation systems deserves further study.     

On the Q.R. algorithm with shift

Fuzzy grammars on Boolean lattices (B-fuzzy grammars) are newly defined and their basic properties are investigated. B-fuzzy grammars are defined as the extension of fuzzy grammars by Lee and Zadeh, where the grades of the application of rewriting rules of B-fuzzy grammars are the elements of Boolean lattice rather than the elements of unit interval [0,1].

It is shown that type 2 B-fuzzy grammars can generate type 1 languages though type 2 fuzzy grammars cannot generate type 2 languages. And the closure properties of B-fuzzy grammars are also studied.     

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.     

Parsing nonlinear languages

The diagrammatic approach to user interfaces for computer-aided software development toolkits, visual query systems, and visual programming environments, is based on the use of diagrams and charts traditionally drawn on paper. In particular, the VLG system (Visual Language Generator) has been proposed to generate icon-oriented visual languages customized for given applications. The syntactical model underlying the interpretation of a visual language in VLG has been designed to describe icon-oriented visual languages. In order to enable the VLG system to apply to any kind of graphical languages, like diagrammatic ones, it is necessary to find a more general syntactical model able to support both their generation and interpretation. This paper addresses the comprehension of the features that a grammatical formalism for nonlinear languages must have to match any requirement for an efficient parsing. To this aim, relation grammars support an easy implementation of a general parsing algorithm for multidimensional languages, parametric with respect to the rewriting rules of the grammar. We compare the expressive power of relation grammars to grammatical formalisms for graph grammars     

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?     

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     

Task-Action Grammars: A Model of the Mental Representation of Task Languages

A formal model of the mental representation of task languages is presented. The model is a metalanguage for defining task-action grammars (TAG): generative grammars that rewrite simple tasks into action specifications. Important features of the model are (a) Identification of the "simple-tasks" that users can perform routinely and that require no control structure; (b) Representation of simple-tasks by collections of semantic components reflecting a categorization of the task world; (c) Marking of tokens in rewrite rules with the semantic features of the task world to supply selection restrictions on the rewriting of simple-tasks into action specifications. This device allows the representation of family resemblances between individual task-action mappings. Simple complexity metrics over task-action grammars make predictions about the relative learnability of different task language designs. Some empirical support for these predictions is derived from the existing empirical literature on command language learning, and from two unreported experiments. Task-action grammars also provide designers with an analytic tool for exposing the configural properties of task languages.     

Hierarchical structures and complexities of parallel isometric languages

The relationship between parallel isometric array languages and sequential isometric array languages is examined. Their hierarchical structures are investigated and a hierarchy is established by introducing parallel context-free array languages (PCFAL), derivation bounded array languages (DBAL), linear array languages (LAL), and extended regular afray languages (ERAL). It is interesting to find that some fundamental aspects that hold in one-dimensional string languages do not hold in their two-dimensional counterparts. Some parsing techniques are also explored. It is shown that while parallel parsing grammars may be simpler to write and parallel processing usually takes less time than sequential ones, the nature of parallel parsing is very complicated. Finally, several future research topics concerned with parallel isometric array languages including their complexities, hierarchical structures, and application to pattern recognition are discussed.     

Selective substitution array grammars

Selective substitution array grammars are introduced, which abstract the notions of rewriting rules, direct derivation steps, derivations and rewriting in a sequential or parallel way. These array grammars provide for a unified framework for many of the two-dimensional array grammars in the literature. In addition, they point towards new interpretations resulting in possible new array grammars.     

Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking

A wide range of parser generators are used to generate parsers for programming languages. The grammar formalisms that come with parser generators provide different approaches for defining operator precedence. Some generators (e.g. YACC) support precedence declarations, others require the grammar to be unambiguous, thus encoding the precedence rules. Even if the grammar formalism provides precedence rules, a particular grammar might not use it. The result is grammar variants implementing the same language. For the C language, the GNU Compiler uses YACC with precedence rules, the C-Transformers uses SDF without priorities, while the SDF library does use priorities. For PHP, Zend uses YACC with precedence rules, whereas PHP-front uses SDF with priority and associativity declarations.The variance between grammars raises the question if the precedence rules of one grammar are compatible with those of another. This is usually not obvious, since some languages have complex precedence rules. Also, for some parser generators the semantics of precedence rules is defined operationally, which makes it hard to reason about their effect on the defined language. We present a method and tool for comparing the precedence rules of different grammars and parser generators. Although it is undecidable whether two grammars define the same language, this tool provides support for comparing and recovering precedence rules, which is especially useful for reliable migration of a grammar from one grammar formalism to another. We evaluate our method by the application to non-trivial mainstream programming languages, such as PHP and C.     

One-sided random context grammars

The notion of a one-sided random context grammar is defined as a context-free-based regulated grammar, in which a set of permitting symbols and a set of forbidding symbols are attached to every rule, and its set of rules is divided into the set of left random context rules and the set of right random context rules. A left random context rule can rewrite a nonterminal if each of its permitting symbols occurs to the left of the rewritten symbol in the current sentential form while each of its forbidding symbols does not occur there. A right random context rule is applied analogically except that the symbols are examined to the right of the rewritten symbol. The paper demonstrates that without erasing rules, one-sided random context grammars characterize the family of context-sensitive languages, and with erasing rules, these grammars characterize the family of recursively enumerable languages. In fact, these characterization results hold even if the set of left random context rules coincides with the set of right random context rules. Several special cases of these grammars are considered, and their generative power is established. In its conclusion, some important open problems are suggested to study in the future.     

On the languages generated by context-sensitive fuzzy grammars

It is proved that the family of the languages generated by 1-fold fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is equal to the family of the context sensitive languages. Also, one shows that the family of the languages generated by fuzzy grammars with context-sensitive rules and grade larger than λ,0≦λ<1, is included in the family of the context-sensitive languages.     

Defining the abstract syntax of visual languages with advanced graph grammars—A case study based on behavior trees

Diagrammatic visual languages can increase the ability of engineers to model and understand complex systems. However, to effectively use visual models, the syntax and semantics of these languages should be defined precisely. Since most diagrammatic visual models that are currently used to specify systems can be described as (directed) typed graphs, graph grammars have been identified as a suitable formalism to describe the abstract syntax of visual modeling languages. In this article, we investigate how advanced graph-transformation techniques, such as conditional, structure-generic and type-generic graph-transformation rules, can help to improve and simplify the specification of the abstract syntax of a visual modeling language. To demonstrate the practicability of an approach that unifies these advanced graph-transformation techniques, we define the abstract syntax of behavior trees (BTs), a graphical specification language for functional requirements. Additionally, we provide a translational semantics of BTs by formalizing a translation scheme to the input language of the SAL model checking tool for each of the graph-transformation rules.     

On restricted context-free grammars

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.     

Time-bounded controlled bidirectional grammars

We study regularly controlled bidirectional (RCB) grammars from the viewpoint of time-bounded grammars. RCB-grammars are context-free grammars of which the rules can be used in a productive and in a reductive fashion, while the application of these rules is controlled by a regular language. Several modes of derivation can be distinguished for this kind of grammar. A time bound on such a grammar is a measure of its derivational complexity. For some families of time bounds and for some modes of derivation we establish closure properties and a normal form theorem. In addition parsing algorithms are given for some modes of derivation. We conclude with considering generalizations with respect to the family of control languages and the family of bounding functions..     

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.