A decidability result for deterministic ω context-free languages

It is shown that the problem whether an effectively given deterministic ω-context-free language is in the family of all closures of deterministic context-free languages is decidable.     

The equivalence of deterministic gsm replications onQ-rational languages is decidable

It is shown that two deterministic gsm replications ₁ and ₂ are equivalent on the supportL of aQ-rational formal power series if and only if ₁ (w) = ₂ (w) for allw inL such that the length ofw does not exceed a certain bound which depends only on the numbers of states in the deterministic gsm's involved and on the size of the matrix system acceptingL. Application of this result to the deterministic gsm equivalence problem improves known bounds. Finally, sufficient conditions for an arbitrary family of languages to have a decidable deterministic gsm replication equivalence problem are presented.     

On pebble automata for data languages with decidable emptiness problem

In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we show that the emptiness problem for weak 2-pebble automata is decidable, while the same problem for weak 3-pebble automata is undecidable. We also introduce the so-called top view weak PA. Roughly speaking, top view weak PA are weak PA where the equality test is performed only between the data values seen by the two most recently placed pebbles. The emptiness problem for this model is still decidable. It is also robust: alternating, non-deterministic and deterministic top view weak PA have the same recognition power; and are strong enough to accept all data languages expressible in Linear Temporal Logic with the future-time operators, augmented with one register freeze quantifier.     

The equivalence problem for deterministic MSO tree transducers is decidable

It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.     

Semantics of context-free languages

Meaning may be assigned to a string in a context-free language by defining attributes of the symbols in a derivation tree for that string. The attributes can be defined by functions associated with each production in the grammar. This paper examines the implications of this process when some of the attributes are synthesized, i.e., defined solely in terms of attributes of thedescendants of the corresponding nonterminal symbol, while other attributes are inherited, i.e., defined in terms of attributes of theancestors of the nonterminal symbol. An algorithm is given which detects when such semantic rules could possibly lead to circular definition of some attributes. An example is given of a simple programming language defined with both inherited and synthesized attributes, and the method of definition is compared to other techniques for formal specification of semantics which have appeared in the literature.     

The inclusion problem for simple languages

A deterministic pushdown acceptor is called a simple machine when it is restricted to have only one state, operate in real-time, and accept by empty store. While the existence of an effective procedure for deciding equivalence of languages accepted by these simple machines is well-known, it is shown that this family is powerful enough to have an undecidable inclusion problem. It follows that the inclusion problems for the LL(k) languages and the free monadic recursion schemes that do not use an identity function are also undecidable.     

Systolic parsing of context-free languages

We report on a new systolic context-free language parsing algorithm. We present both single parse and multiple parse versions of the algorithm. For an input of lengthn the single parse version has a time complexity ofO(n) and a space complexity ofO(n) ². This equals the performance of the most effcient known single parse algorithm. The space complexity of the multiple parse version is also ofO(n) ² while its time complexity is ofO(mn) wherem is the number of differenti parses for the input. This equals the time complexity of the most efficient known multiple parse algorithms and brings an improvenment of a factor of logn over its space complexity.This work was supported by Université de Montréal, the Natural Science Engineering Resarch Council of Canada and the Communittee of Vice-Chancellors and Principals of the Universities of the United Kingdom.     

The Turing degree of the inherent ambiguity problem for context-free languages

The inherent ambiguity question for context-free languages is shown to be in the Turing degree of unsolvability O”. The method used is to show that the inherent ambiguity question is equivalent to the finiteness question for r.e. sets which is in degree O”. The proof associates a context-free language with each Turing machine. The language has a natural closed-form definition in terms of the Turing machine. The associated language is inherently ambiguous precisely iof the Turing machine accepts an infinite set.     

A strong pumping lemma for context-free languages

A context-free language is shown to be equivalent to a set of sentences describable by sequences of strings related by finite substitutions on finite domains, and vice-versa. As a result, a necessary and sufficient version of the Classic Pumping Lemma is established. This result provides a guaranteed method of proving that a language is not context-free when such is the case. An example is given of a language which neither the Classic Pumping Lemma nor Parikh's Theorem can show to be non-context-free, although Ogden's Lemma can. The main result also establishes {aⁿba^mn} as a language which is not in the Boolean closure of deterministic context-free languages.