Stochastic grammars and languages

This paper summarizes some recent results concerned with the extension of formal languages to their corresponding stochastic versions. Weighted grammars and languages are first defined, and stochastic grammars and languages are defined as a special case of weighted grammars and languages. Fuzzy grammars and languages, which have some properties similar to weighted grammars and languages, are also discussed. Stochastic automata are defined from the language recognition viewpoint. Languages accepted by stochastic finite-state and pushdown automata, with and without a cutpoint, are studied. Weighted and stochastic programmed and indexed grammars, and stochastic nested stack automata are defined. Finally, some decidability problems of stochastic (weighted, fuzzy) languages are discussed, and problems for further research are suggested.This work was supported by the National Science Foundation Grant GK-18225.     

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.     

Circular attribute grammars with remote attribute references and their evaluators

Attribute grammars (AGs) are a suitable formalism for the development of language processing systems. However, for languages including unrestricted labeled jumps, such as “goto” in C, the optimizers in compilers are difficult to write in AGs. This is due to two problems that few previous researchers could deal with simultaneously, i.e., references of attribute values on distant nodes and circularity in attribute dependency. This paper proposescircular remote attribute grammars (CRAGs), an extension of AGs that allows (1) direct relations between two distant attribute instances through pointers referring to other nodes in the derivation tree, and (2) circular dependencies, under certain conditions including those that arise from remote references. This extension gives AG programmers a natural means of describing language processors and programming environments for languages that include any type of jump structure. We also show a method of constructing an efficient evaluator for CRAGs called amostly static evaluator. The performance of the proposed evaluator has been measured and compared with dynamic and static evaluators. Akira Sasaki: He is a research fellow of the Advanced Clinical Research Center in the Institute of Medical Science at the University of Tokyo. He received his BSc and MSc from Tokyo Institute of Technology, Japan, in 1994 and 1996, respectively. His research interests include programming languages, programming language processors and programming environments, especially compiler compilers, attribute grammars and systematic debugging. He is a member of the Japan Society for Software Science and Technology. Masataka Sassa, D.Sc.: He is Professor of Computer Science at Tokyo Institute of Technology. He received his BSc, MSc and DSc from the University of Tokyo, Japan, in 1970, 1972 and 1978, respectively. His research interests include programming languages, programming language processors and programming environments, currently he is focusing on compiler optimization, compiler infrastructure, attribute grammars and systematic debugging. He is a member of the ACM, IEEE Computer Society, Japan Society for Software Science and Technology, and Information Processing Society of Japan.     

An on-the-fly grammar modification mechanism for composing and defining extensible languages

Adaptable Parsing Expression Grammar (APEG) is a formal method for defining the syntax of programming languages. It provides an on-the-fly mechanism to perform modifications of the syntax of the language during parsing time. The primary goal of this dynamic mechanism is the formal specification and the automatic parser generation for extensible languages. In this paper, we show how APEG can be used for the definition of the extensible languages SugarJ and Fortress, clarifying many aspects of the syntax of these languages. We also show that the mechanism for on-the-fly modification of syntax rules can be useful for defining grammars in a modular way, implementing almost all types of language composition in the context of specification of extensible languages.     

A game-theoretic characterization of Boolean grammars

We obtain a simple, purely game-theoretic characterization of Boolean grammars [A. Okhotin, Boolean grammars, Information and Computation, 194(1) (2004) 19–48]. In particular, we propose a two-player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. The game is directly applicable to the simpler classes of conjunctive and context-free grammars, and offers a promising new connection between game theory and formal languages.     

Spinal-Formed Context-Free Tree Grammars

In this paper we introduce a restricted model of context-free tree grammars called spine grammars, and study their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It is shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduce acceptors called linear pushdown tree automata, and show that linear pushdown tree automata accept exactly the class of tree languages generated by spine grammars. Linear pushdown tree automata are obtained from pushdown tree automata with a restriction on duplicability for the pushdown stacks. Received May 29, 1998, and in revised form April 27, 1999, and in final form May 10, 1999.     

Fuzzy multiset finite automata and their languages

Inspired by the generalizations from grammars and finite automata to fuzzy grammars and fuzzy finite automata, respectively, we introduce the concepts of fuzzy multiset grammars and fuzzy multiset finite automata (FMFAs), as the generalizations of multiset grammars and multiset finite automata, respectively. The relationship between fuzzy multiset regular grammars and FMFAs is discussed. Furthermore, we define some operations on fuzzy multiset languages, and prove that the family of FMFA languages is closed under the operations.     

Event-driven grammars: relating abstract and concrete levels of visual languages

In this work we introduce event-driven grammars, a kind of graph grammars that are especially suited for visual modelling environments generated by meta-modelling. Rules in these grammars may be triggered by user actions (such as creating, editing or connecting elements) and in their turn may trigger other user-interface events. Their combination with triple graph transformation systems allows constructing and checking the consistency of the abstract syntax graph while the user is building the concrete syntax model, as well as managing the layout of the concrete syntax representation. As an example of these concepts, we show the definition of a modelling environment for UML sequence diagrams. A discussion is also presented of methodological aspects for the generation of environments for visual languages with multiple views, its connection with triple graph grammars, the formalization of the latter in the double pushout approach and its extension with an inheritance concept. This is a revised and extended version of a paper presented at the ICGT’04 conference, see [21].     

Highly Constrained Unification Grammars

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the constraint and show that one-reentrant unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages.     

Horn逻辑程序和形式文法之间的对应关系

The paper researches Horn logic programs with grammatical view. The correspondence between Horn logic programs and grammars is found. The method by which type-0 grammars generate the least Herbrand models of logic programs is found. The method by which Horn logic programs generate the languages of type-0 grammars is found.The characterization of Horn Logic programs that are semantically equavanent to type-2 grammars and type-3 grammars is found.     

Approximation of fuzzy context-free grammars

Fuzzy context-free max- grammar (or FCFG, for short), as a straightforward extension of context-free grammar, has been introduced to express uncertainty, imprecision, and vagueness in natural language fragments. Li recently proposed the approximation of fuzzy finite automata, which may effectively deal with the practical problems of fuzziness, impreciseness and vagueness. In this paper, we further develop the approximation of fuzzy context-free grammars. In particular, we show that a fuzzy context-free grammar under max- compositional inference can be approximated by some fuzzy context-free grammar under max-min compositional inference with any given accuracy. In addition, some related properties of fuzzy context-free grammars and fuzzy languages generated by them are studied. Finally, the sensitivity of fuzzy context-free grammars is also discussed.     

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.     

One application of real-valued interpretation of formal power series

We define two natural properties of context-free grammars. The first property generalizes linearity and the second property strengthens nonlinearity. A language generated by an unambiguous grammar of the first type is called the language with weak linear structure and a language generated by an unambiguous grammar of the second type is called the language with strong nonlinear structure. Our main theorem states that the family of unambiguous grammars generating languages with weak linear structure and the family of unambiguous grammars generating languages with strong nonlinear structure are effectively separable.     

Restrictions, extensions, and variations of NLC grammars

This paper continues the basic research on node-label-controlled graph grammars (NLC grammars). In particular three topics are investigated quite thoroughly: (1) the role of the connection relation in an NLC grammar, (2) “context-freeness” of NLC grammars, and (3) the ability of NLC grammars to generate string languages.     

Recursive descent parsing for Boolean grammars

The recursive descent parsing method for the context-free grammars is extended for their generalization, Boolean grammars, which include explicit set-theoretic operations in the formalism of rules and which are formally defined by language equations. The algorithm is applicable to a subset of Boolean grammars. The complexity of a direct implementation varies between linear and exponential, while memoization keeps it down to linear. Supported by the Academy of Finland under grant 118540.     

Linearity and nondeletion on monadic context-free tree grammars

In this paper, subclasses of monadic context-free tree grammars (CFTGs) are compared. Since linear, nondeleting, monadic CFTGs generate the same class of string languages as tree adjoining grammars (TAGs), it is examined whether the restrictions of linearity and nondeletion on monadic CFTGs are necessary to generate the same class of languages.     

The Generating Power of Total Deterministic Tree Transducers

Attributed tree transducers are abstract models used to study properties of attribute grammars. One abstraction which occurs when modeling attribute grammars by attributed tree transducers is that arbitrary trees over a ranked alphabet are taken as input, instead of derivation trees of a context-free grammar. In this paper we show that with respect to the generating power this isnotan abstraction; i.e., we show that attributed tree transducers and attribute grammars generate the same class of term (or tree) languages. To prove this, a number of results concerning the generating power of top-down tree transducers are established, which are interesting in their own. We also show that the classes of output languages of attributed tree transducers form a hierarchy with respect to the number of attributes. The latter result is achieved by proving a hierarchy of classes of tree languages generated by context-free hypergraph grammars with respect to their rank.     

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.     

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).     

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.