The equivalence problem for two dpda's,one of which is a finite-turn or one-counter machine

For some non-real-time subclasses $\text{C}$ of deterministic pushdown automata (dpda), we give a general scheme to extend a decision procedure of the equivalence to that for two dpda's, one of which is in $\text{C}$. Using this scheme, we prove that the equivalence problem is decidable for two dpda's, one of which is a finite-turn or one-counter machine.     

A note on non-singular deterministic pushdown automata

The non-singular deterministic pushdown automata were first defined by Valiant as an example of a class of machines with a decidable equivalence problem [3]. No algorithm currently exist for deciding whether or not a deterministic pushdown automation is non-singular, so the applicability of Valiant's equivalence decision procedure cannot be readily (if ever) determined. In this paper, it is shown that the equivalence problem for non-singular automata is reducible to the problem of deciding whether or not a deterministic pushdown automaton is non-singular.     

Simple context-free languages and free monadic recursion schemes

A context-free language is said to be simple if it is accepted by a single-state deterministic pushdown store acceptor that operates in real-time and accepts by empty store. While the problem remains open of deciding whether or not the language accepted by a deterministic pushdown store acceptor is simple, it is shown that this problem is equivalent to another problem in schemata theory. This question is that of determining whether or not a monadic recursion scheme has a strongly equivalent free scheme.This research was supported in part by the National Science Foundation, Grant No. NSF GJ-803 and DCR74-15091.     

Reversible pushdown automata

Reversible pushdown automata are deterministic pushdown automata that are also backward deterministic. Therefore, they have the property that any configuration occurring in any computation has exactly one predecessor. In this paper, the computational capacity of reversible computations in pushdown automata is investigated and turns out to lie properly in between the regular and deterministic context-free languages. Furthermore, it is shown that a deterministic context-free language cannot be accepted reversibly if more than realtime is necessary for acceptance. Closure properties as well as decidability questions for reversible pushdown automata are studied. Finally, we show that the problem to decide whether a given nondeterministic or deterministic pushdown automaton is reversible is P-complete, whereas it is undecidable whether the language accepted by a given nondeterministic pushdown automaton is reversible.     

A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars

We present here an equivalence checking algorithm which operates directly on a pair of strict deterministic vs. LL(k) grammars. It is also straightforwardly applicable to a pair of LL(k) grammars, though an LL(k) grammar is not necessarily strict deterministic. The basic idea is from Korenjak and Hopcroft's branching algorithm for simple deterministic grammars, but ours is so distinguished that it is throughout free from mixing the nonterminals of the respective grammars in question and then very simple.     

On LR(k) grammars and languages

Many different definitions for LR(k) grammars exist in the literature. One of these definitions is chosen and many important implications are drawn from it. In particular, the LR(k) characterization theorem provides valuable information about chains of derivations. The LR(0) languages are then characterized by acceptance by deterministic pushdown automata with a special termination condition, by a condition on the strings in the language, and set theoretically. Important closure properties of the LR(0) languages and a related class of languages are then examined. These are used to examine some decidability questions relating to the class of LR languages. One of these questions is shown to be equivalent to the equality problem for deterministic pushdown automata.A survey of other LR(k) definitions is given and the exact differences are characterized. On the basis of this analysis, justification for the choice of definition used here is provided.     

Morphismes et bimorphismes d'arbres

For every pair of positive integers n and p, there is a language accepted by a real-time deterministic pushdown automaton with n states and p stack symbols and size O(np), for which every context-free grammar needs at least n²p+1 nonterminals if n>1 (or p non-terminals if n = 1). It follows that there are context-free languages which can be recognized by pushdown automata of size O(np), but which cannot be generated by context-free grammars of size smaller than O(n²p); and that the standard construction for converting a pushdown automaton to a context-free grammar is optimal in the sense that it infinitely often produces grammars with the fewest number of nonterminals possible.     

Simple chain grammars and languages

A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar.Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.     

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 regular tree languages and deterministic pushdown automata

The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an LR(0) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.     

A characterization of s-languages

We show that a language L is an s-language if and only if the set of the quotients of L (i.e., the set of the states of its minimal deterministic automaton seen as languages) is a subset of a free monoid generated by a finite set of prefix codes. We demonstrate through examples how to use this result for deciding whether a given language is an s-language.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

Pushdown Processes: Games and Model-Checking

A pushdown game is a two player perfect information infinite game on a transition graph of a pushdown automaton. A winning condition in such a game is defined in terms of states appearing infinitely often in the play. It is shown that if there is a winning strategy in a pushdown game then there is a winning strategy realized by a pushdown automaton. An EXPTIME procedure for finding a winner in a pushdown game is presented. The procedure is then used to solve the model-checking problem for the pushdown processes and the propositional μ-calculus. The problem is shown to be DEXPTIME-complete.     

Finite automata for testing composition-based reconstructibility of sequences

Symbolic sequences uniquely reconstructible from all their substrings of length k compose a regular factorial language. We thoroughly characterize this language by its minimal forbidden words, and explicitly build up a deterministic finite automaton that accepts it. This provides an efficient on-line algorithm for testing the unique reconstructibility of the sequences.     

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.     

A note on deciding controllability in pushdown systems

Consider an event alphabet /spl Sigma/. The supervisory control theory of Ramadge and Wonham asks the question, given a plant model G, with language K L/sub M/(G)/spl sube//spl Sigma//sup */ and another language K/spl sube/ L/sub M/(G), is there a supervisor /spl psi/ such that L/sub M/(/spl psi//G)=K. Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of K with respect to L/sub M/(G). They showed that when G is a finite state automaton and K is a regular language (also generated by a finite state automaton), then the controllability property was decidable for K. The class of languages generated by pushdown automata properly includes the regular languages. They are accepted by finite state machines coupled with pushdown stack memory. This makes them interesting candidates as supervisory languages, since the supervisor will have nonfinite memory. In this note, we show the following: i) If S is a specification given by a deterministic pushdown automaton and L is generated by a finite state machine, then there is an algorithm to decide whether K=S/spl cap/L is controllable with respect to L. ii) It is undecidable for an arbitrary specification S generated by a nondeterministic pushdown automaton and plant language L generated by a finite state machine whether K=S/spl cap/L is controllable with respect to L.     

Finite automata with multiplication

A finite automaton with multiplication (FAM) is a finite automaton with a register which is capable of holding any positive rational number. The register can be multiplied by any of a fixed number of rationals and can be tested for value 1. Closure properties and decision problems for various types of FAM's (e.g. two-way, one-way, nondeterministic, deterministic) are investigated. In particular, it is shown that the languages recognized by two-way deterministic FAM's are of tape complexity log n and time complexity n³. Some decision problems related to vector addition systems are also studied.     

A note on three-dimensional finite automata

This paper investigates the relationships between the accepting powers of three-dimensional six-way finite automata (3-FA's) and three-dimensional five-way Turing machines (5WTM's), where the input tapes of these automata are restricted to cubic ones. A 3-FA (5WTM) can be considered as a natural extension of the two-dimensional four-way finite automaton (two-dimensional three-way Turing machine) to three dimensions. The main results are: (1) n²logn (n³) space is necessary and sufficient for deterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's; (2) n² (n²) space is necessary and sufficient for nondeterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's.     

A direct algorithm for checking equivalence of LL(k) grammars

We deal with the problem of testing equivalence of two LL(k) grammars. The problem had been shown to be decidable for general k by Rosenkrantz and Stearns [2], who solved it by reduction into an equivalence problem for special DPDA's. In a paper by Korenjak and Hopcroft [1] the equivalence problem for LL(1) grammars is solved by a branching algorithm operating directly on the grammars. Our work presents a direct branching algorithm for the general LL(k) grammars equivalence problem.