Look-ahead on pushdowns

The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the non-deterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look-ahead on the input, and LL-regular iterated indexed grammars.     

On languages of automaton counter machines

A class of formal languages (ACML) acceptable by automaton counter machines is considered. This class is shown to be close with respect to the operations of union, regular intersection, concatenation, infinite iteration, homomorphism, and inverse homomorphism. It follows from here that this class is a full abstract family of languages [7] with all the properties following from this. Furthermore, the ACML is close with respect to intersection and substitution but is not closed with respect to complement and reverse. For the ACML class, the problems of emptiness and recognition of words of a language given by an automaton counter machine are decidable, but the problems of inclusion and equivalence of languages are undecidable. A comparison with other classes of languages (regular, context-free, context-sensitive, and Petri-net languages) is performed.     

Timing Diagrams: Formalization and Algorithmic Verification

Timing diagrams are popular in hardware design. They have been formalized for use in reasoning tasks, such as computer-aided verification. These efforts have largely treated timing diagrams as interfaces to established notations for which verification is decidable; this has restricted timing diagrams to expressing only regular language properties. This paper presents a timing diagram logic capable of expressing certain context-free and context-sensitive properties. It shows that verification is decidable for properties expressible in this logic. More specifically, it shows that containment of -regular languages generated by Büchi automata in timing diagram languages is decidable. The result relies on a correlation between timing diagram and reversal bounded counter machine languages.     

Derivation languages of grammar forms†

The family of derivation languages or Szilard languages associated with a grammar form is studied. It is shown that Szilard equivalence, regular completeness and regular sufficiency are decidable properties. Although the decidability of left Szilard equivalence remains open, we reduce this problem to the equivalence problem for a special class of s-grammar forms     

On the language equivalence of NE star-patterns

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. The pattern languages are one of language family which is orthogonal to the Chomsky-type languages hierarchy. They have many applications, such as the extended regular expressions, for instance, in languages Perl, awk, etc. They are well applicable in machine learning as well. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star still open. In this paper there are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages. We show that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties. These results may be useful to decide whether the language equivalence of non-erasing star-patterns is decidable or not.     

Two-way counter machines and finite-state transducers†

Consider the emptiness problem for deterministic two-way finite-state automata that are augmented by a bounded-reversal counter and the equivalence problem for deterministic two-way finite-state transducers. The first problem was posed by Ibarra while the second problem restricted to the case that accepting configurations are also halting configurations was posed by Ehrich and Yau. Recently the first problem restricted to devices that accept only bounded languages as well as the restricted version of the second problem have been shown decidable. Here these two problems are shown decidable also in their general form.     

Equivalence of conservative,free, linear program schemas is decidable

A program schema defines a class of programs, all of which have identical statement structures, but whose expressions may differ. We prove that given any two structured schemas which are conservative, linear and free, it is decidable whether they are equivalent.     

Decision problems concerning thinness and slenderness of formal languages

A language L is called thin if for almost all n there is at most one word of length n in L. A language L is called slender if there is a positive integer k such that for any n there are at most k words of length n in L. The notions of Parikh thin and Parikh slender languages are defined similarly by counting the words with the same Parikh vectors instead of the words of the same length. In this paper we discuss decision problems concerning these four properties. It is shown that all four properties are decidable for bounded semilinear languages but undecidable for DT0L languages. As a consequence all these problems are decidable for context-free languages. Received 9 June 1997 / 3 December 1997     

Monadic recursion schemes: The effect of constants

When the class of monadic recursion schemes is augmented by individual constants, some of the properties change. It becomes undecidable whether “S diverges” or “S is strongly equivalent to T” for S, T schemes with individual constants. The family of value languages generated by this class of schemes is the family of recursively enumerable languages. The subclass of free schemes with constants is also investigated. It remains decidable whether “S halts” or “S diverges” for S a free scheme with individual constants, but it becomes undecidable whether “T has a strongly equivalent free scheme” for T an arbitrary scheme with individual constants.     

On sentential forms of context-free grammars

Summary There is no algorithm for deciding whether two linear context-free grammars generate the same sentential forms. The equivalence problem for propagatingOL-systems is undecidable. The finiteness problem forOL-systems is decidable.SF-languages, i.e., languages which equal the set of sentential forms of a context-free grammar, possess some of the properties of context-free languages but their family is not closed under any of the ordinary operations.     

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.     

Multipass precedence analysis

Summary This paper defines a hierarchy of languages which is properly contained in the context sensitive languages and which starts with the context free family. The hierarchy is defined inductively by controlling labeled linear grammars with languages in one family to yield languages in the next larger family. The families of the hierarchy have properties analogous to those of the context free family, in particular, the new mechanism introduced is very suitable for parsing.A language in the n-th family is specified by a sequence of n — 1 labeled linear grammars and a context free grammar. By assuming that the reversals of the first n — 1 grammars and the last labeled linear grammar are precedence grammars, the concepts and parsing algorithm of Wirth and Weber extend to yield a parsing algorithm within the hierarchy. This considerably enhances the usefulness of the construction and allows much of the power of the context sensitive languages to become accessible in measured amounts for potential programming applications.     

The membership and equivalence problems for picture languages

The paper describes two principal results: (1) there is a nondeterministic polynomial-time algorithm to determine whether an arbitrary picture is a member of a context-free picture language and (2) the equivalence problem for regular picture languages is not decidable (not even partially decidable). This solves open questions described in earlier publications. Furthermore, these results are best possible. That is, the membership problem for context-free picture languages was earlier shown to be NP-hard and the complement of the equivalence problem for regular picture languages is easily seen to be partially decidable.     

On DOL systems with immigration

We study DOL systems with immigration. We show that sequence and growth equivalence are decidable. We establish regularity and decidability results concerning degrees of ambiguity. As a consequence of results about subword complexity, we show that regularity and ω-regularity are decidable for languages generated by growing systems.     

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.     

On a family of L languages resulting from systolic tree automata

Recent work on systolic tree automata has given rise to a rather natural subfamily of EOL languages, referred to as systolic EOL languages in this paper. Systolic EOL languages possess some remarkable properties. While their family contains (because of its closure under Boolean operations) intuitively quite complicated languages, it still has decidable equivalence problem. Especially interesting is the fact that similar decision problems for slightly more general families lead to the celebrated open problems concerning Z-rational power series.     

Optimization schemas for parallel implementation of non‐deterministic languages and systems

Naive parallel implementation of non‐deterministic systems (such as a theorem proving system) and languages (such as logic, constraint, or concurrent constraint languages) can result in poor performance. We present three optimization schemas, based on flattening of the computation tree, procrastination of overheads, and sequentialization of computations that can be systematically applied to parallel implementations of non‐deterministic systems/languages to reduce the parallel overhead and to obtain improved efficiency of parallel execution. The effectiveness of these schemas is illustrated by applying them to the ACE parallel logic programming system. The performance data presented show that considerable improvement in execution efficiency can be achieved. Copyright © 2001 John Wiley & Sons, Ltd.     

Termination Proofs for String Rewriting Systems via Inverse Match-Bounds

Annotating a letter by a number, one can record information about its history during a rewrite derivation. In each rewrite step, numbers in the reduct are updated depending on the redex numbering. A string rewriting system is called match-bounded if there is a global upper bound to these numbers. Match-boundedness is known to be a strong sufficient criterion for both termination and preservation of regular languages. We show that the string rewriting systems whose inverse (left and right hand sides exchanged) is match-bounded, also have exceptional properties, but slightly different ones. Inverse match-bounded systems need not terminate; they effectively preserve context-free languages; their sets of normalizable strings and their sets of immortal strings are effectively regular. These languages can be used to decide the normalization, the uniform normalization, the termination and the uniform termination problem for inverse match-bounded systems. We also prove that the termination problem is decidable in linear time, and that a certain strong reachability problem is decidable, thereby solving two open problems of McNaughton’s. Like match-bounds, inverse match-bounds entail linear derivational complexity on the set of terminating strings.     

NTS languages are deterministic and congruential

A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove here that such grammars generate deterministic languages which are finite unions of congruence classes. Moreover, we show that this family of languages is closed under reversal and intersection with regular sets. A forthcoming paper will prove that, for this class, the equivalence problem is decidable.     

Fifo nets without order deadlock

Summary We introduce a generalisation of free choice nets to fifo. These fifo nets are free from deadlocks caused by the order of messages in fifo queues. We describe some tools for their analysis, using the fact that they are weakly monotonous, and that there is a narrow relation between their languages and those of the associated coloured nets. Therefore, quasi-liveness, finite termination and liveness are decidable properties.