Search

The regulated rewriting mechanism is one of the most efficient methods to augment the Chomsky hierarchy with a large variety of language classes. In this paper we investigate the derivation mechanism in regulated rewriting grammars such as matrix grammars, by studying their Szilard languages. We focus on the complexity of Szilard languages associated with unrestricted and leftmost-like derivations in matrix grammars, with or without appearance checking. The reason is twofold. First, to relate these classes of languages to parallel complexity classes such as NC1 and AC1, and, second, to improve some previous results. We prove that unrestricted Szilard languages and certain leftmost Szilard languages of context-free matrix grammars, without appearance checking, can be accepted by indexing alternating Turing machines in logarithmic time and space. Consequently, these classes are included in UE*-uniform NC1. Unrestricted Szilard languages of matrix grammars with appearance checking can be accepted by deterministic Turing machines in On log n time and Olog n space. Leftmost-like Szilard languages of context-free matrix grammars, with appearance checking, can be recognized by nondeterministic Turing machines by using the same time and space resources. Hence, all these classes are included in AC1.

Contextual grammars are introduced by Solomon Marcus in 1969 based on the fundamental concept of descriptive linguistics of insertion of strings in given contexts. Internal contextual grammars are introduced by Paun and Nguyen in 1980. For contextual grammars several descriptional complexity measures and levels of ambiguity have been defined. In this paper, we analyze the trade-off between ambiguity and complexity of languages generated by internal contextual grammars. The notion of a pseudo inherently ambiguous language with respect to two complexity measures is introduced and investigated. These languages can be generated by unambiguous grammars which are minimal with respect to one measure and ambiguous if they are minimal with respect to the other measure. An open problem from [15] is solved in this framework.

Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions.

Growing context-sensitive grammars were introduced in 1986 as a restricted variant of context-sensitive grammars, where all productions are length increasing. Several interesting properties of these grammars have been shown since then, including polynomial time complexity of the membership problem and machine model characterizations. Various characterizations of the model, efficient recognition algorithm and the properties of its deterministic variant (possessing a characterization by string-rewriting systems) justify the practical value. Moreover, as pointed out by McNaughton in 1999, growing context-sensitive grammars complement the Chomsky hierarchy in a very natural way. This article reviews results on this topic and proposes some open problems.

In this paper we investigate insertion grammars and explore their capacity to generate words parallelly by introducing parallel derivation (where more than one rule can be applied to the string in parallel) and maximum parallel derivation (where as many rules as possible are applied to the string in parallel). We compare the generative power of these grammars with context sensitive and context free grammars and with different variants of contextual grammars. We apply these grammars to syllabification in Romanian and provide arguments that they can also be used in a cognitive perspective.

We study the generative capacity of multi-bracketed contextual rewriting grammars. This model is a generalization of multi-bracketed contextual grammars, which were studied in [Kap98a]. They possess an induced Dyck-structure to control the derivation process and to provide derivation trees. The generative capacity of this class is investigated and compared to Chomsky grammars and to tree adjoining grammars with local constraints. It will be shown that this class of grammars covers the basic natural language constructions such as duplication, multiple agreement and crossed-serial dependencies. Furthermore, two natural variants of the derivation relation, namely top-down and bottom-up derivation modes are examined.

The grammatical inference problem is solved for a class of languages which can be generated by pure grammars with non-shortening productions. Necessary and sufficient condition for determination whether a language belongs to this class is formulated and proved. Finally, an algorithm for assigning a pure grammar to any language from the class is described.

The paper provides a structural characterisation of the reachable markings of Petri nets in which every transition has exactly one input place. As a corollary, the reachability problem for this class is proved to be NP-complete. Further consequences are: the uniform word problem for commutative context-free grammars is NP-complete; weak-bisimilarity is semidecidable for Basic Parallel Processes.

We consider here some special forms of ambiguity for pure context-free grammars, namely pattern avoiding ambiguity, pattern preserving ambiguity, pattern ambiguity, and grammar avoiding ambiguity. The first two properties are undecidable for arbitrary pure context-free grammars, and in a particular but general enough case we can effectively decide whether or not a pure context-free grammar is pattern preserving ambiguous.

The use of regular tree grammars to represent and build models of formulae of first-order logic without equality is investigated. The combination of regular tree grammars with equational constraints provides a powerful and general way of representing Herbrand models. We show that the evaluation problem (i.e. the problem of finding the truth value of a formula in a given model) is decidable when models are represented in the way we propose. We also define a method to build such representations of models for first-order formulae. These results are a powerful extension of our former method for simultaneous search for refutations and models.

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 their generative capacity we obtain an infinite hierarchy of languages that comprises the context-free ones as the first and all those generated by Tree Adjoining Grammars (TAGs) as the second element. The latter is important because today, TAGs are commonly used to model the syntax of natural languages. Here, we present a completely new approach to analyse this language hierarchy. It solves the word problem for the class of languages generated by TAGs in time O(n 6), n length of the input, by reducing it to the analysis of sequences of parentheses. (This research has been supported by a Graduiertenkolleg-fellowship of the Deutsche Forschungs-gemeinschaft and by the ESPRIT Basic Research Action No. 6317 (ASMICS2).)

Continuing the work begun in [14], we consider contextual grammars (as introduced in [6] with linguistic motivation) with parallel derivations, in which the whole current string participates to a derivation step in the sense that it is splitted into substrings to which contexts are adjoined in a parallel manner. The generative power of such grammars is investigated, when the parallelism is total or partial, and when the selection of contexts is limited to strings in sets of a given type (finite, regular etc.) Then we consider the languages consisting of strings which cannot be further derived (we call them blocking languages). Some open problems are also formulated.

Collage grammars are based on hyperedge replacement in a geometric environment and provide context-free syntactic devices for the generation of picture languages. An intriguing question is which geometric properties of the generated pictures can be decided by inspecting the generating collage grammars. The results presented in this paper address the question in two respects. (1) The decidability results known for hyperedge replacement grammars generating graph languages, based on the notion of compatibility, can be carried over to collage grammars. Unfortunately, compatible properties seem rare in the geometric setting. In this paper three concrete ones are presented. (2) In some other cases being only a minor extensions of situations for which compatibility is obtained, we can prove undecidability results.

We introduce terminally coded (TC) grammars, which generalize parenthesis grammars in the sense that from each word ω generated by a TC grammar we can recover the unlabeled tree t underlying its derivation tree(s). More precisely, there is a length-preserving homomorphism that maps ω to an encoding of t. Basic properties of TC grammars are established. For backwards deterministic TC grammars we give a shift-reduce precedence parsing method without look-ahead, which implies that TC languages can be recognized in linear time. The class of TC languages contains all parenthesis languages, and is contained in the classes of simple precedence languages and NTS languages.

This paper introduces a machinery called attributed top-down parsing automaton which performs top-down parsing of strings and, simultaneously, the evaluation of arbitrary noncircular attribute grammars. The strategy of the machinery is based on a single depth-first left-to-right traversal over the syntax tree. There is no need to traverse parts of the syntax tree more than once, and hence, the syntax tree itself does not have to be maintained. Attribute values are stored in a graph component, and values of attributes which are needed but not yet computed are represented by particular nodes. Values of attributes which refer to such uncomputed attributes are represented by trees over operation symbols in which pointers to the particular nodes at their leaves are maintained. Whenever eventually the needed attribute value is computed, it is glued into the graph at the appropriate nodes.

This note studies the conjecture that context-free matrix languages over one-letter alphabet are regular. We are able to confirm the conjecture in a special case where at most one non terminal can have an unbounded number of occurrences in sentential forms.