Deciding Emptiness for Stack Automata on Infinite Trees

We show that the emptiness problem for Büchi stack automata on infinite trees is decidable in elementary time. We first establish the decidability of the emptiness problem for pushdown automata on infinite trees. This is done using a pumping-like argument applied to computation trees. We then show how to reduce the emptiness problem for stack automata to the emptiness problem for pushdown automata. Elsewhere, we have used the result to establish the decidability of several versions of nonregular dynamic logic.     

Decision problems for pushdown threads

Threads as contained in a thread algebra emerge from the behavioral abstraction from programs in an appropriate program algebra. Threads may make use of services such as stacks, and a thread using a single stack is called a pushdown thread. Equivalence of pushdown threads is shown decidable whereas pushdown thread inclusion is undecidable. This is again an example of a borderline crossing where the equivalence problem is decidable, whereas the inclusion problem is not.     

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.     

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.     

Complexity results for classes of quantificational formulas

We analyze the computational complexity of determining whether F is satisfiable when F is a formula of the classical predicate calculus obeying certain syntactic restrictions. For example, for the monadic predicate calculus and the Gödel or 3 … ???? … 3 prefix class we obtain lower and upper nondeterministic time bounds of the form c^{n/log n}. The lower bounds are established by using acceptance problems for time-bounded Turing machines and alternating pushdown and stack automata.     

An algebraic characterization of some principal regulated rational cones

The aim of this paper is to deal with formal power series over a commutative semiring A. Generalizing Wechler's pushdown automata and pushdown transition matrices yields a characterization of the A-semi-algebraic power series in terms of acceptance by pushdown automata. Principal regulated rational cones generated by cone generators of a certain form are characterized by algebraic systems given in certain matrix form. This yields a characterization of some principal full semi-AFL's in terms of context-free grammars. As an application of the theory, the principal regulated rational cone of one-counter “languages” is considered.     

A NEW AUTOMATON MODEL FOR TAGS: 2-SA

In this paper, we introduce and define a new class of automata (pushdown automata with n stacks, abbreviated as n-SA). The ultimate aim is to give a new characterization of LCRFL, the class of languages accepted by a linear context-free rewriting system (LCFRS). In particular, we introduce 2-SA as a new automaton model for tree-adjoining grammars (TAG). In the simplest cases (0-SA and 1-SA), the languages that are accepted by the automata are the regular and context-free languages respectively. A more complex case is the case of a 2-SA which accepts TALs. The n-SA creates an infinite hierarchy of languages and it seems that this hierarchy corresponds to others in the class LCFRL. The 2-SA corresponds closely to the EPDA (embedded pushdown automaton, an automaton model equivalent to TAGs). Unlike the EPDA, which allows push operations "below the top stack," an n-SA allows push and pop operations only on the top of their (multiple) stacks. So n-SA trade simpler operations against an also simpler but expanded storage structure.     

Tree-stack automata

We introduce a new model of stack automata, the “tree-stack automata,” extending the linear stack to a tree-stack. A main subject of our investigations is to explore the relationship between tree-stack automata and stack automata. The main result of this paper is that tree-stack have the same recognition power as stack-pushdown automata, another (well-known) extension of stack automata. Therefore we obtain that the class of languages accepted by the one-way (linear) stack automata is a proper subset of the class of languages accepted by the one-way tree-stack automata and that two-way tree-stack automata have the same recognition power as two-way (linear) stack automata. As a special case of tree-stack automata we consider tree-pushdown automata. As opposed to stack automata the tree-pushdown storage does not extend the recognition power of one-way (resp. two-way) pushdown automata.     

Some Properties of Iterated Languages

A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses of natural language quantifiers. We also determine the state complexity of iteration of regular languages.     

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.     

Propositional dynamic logic with recursive programs

We extend the propositional dynamic logic PDL of Fischer and Ladner with a restricted kind of recursive programs using the formalism of visibly pushdown automata [R. Alur, P. Madhusudan, Visibly pushdown languages, in: Procceings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), 2004, ACM, pp. 202–211]. We show that the satisfiability problem for this extension remains decidable, generalising known decidability results for extensions of PDL by non-regular programs. Our decision procedure establishes a 2-ExpTime upper complexity bound, and we prove a matching lower bound that applies already to rather weak extensions of PDL with non-regular programs. Thus, we also show that such extensions tend to be more complex than standard PDL.     

Approximating bisimulation in one-counter nets

One-counter nets are finite-state machines operating on a variable (counter), which ranges over the natural numbers. Each transition can increase or decrease the counter’s value, and a decrease is possible only if the result is nonnegative; hence, zero testing is not allowed. The class of one-counter nets is equivalent in terms of its expressive power to the class of Petri nets with one unbounded place and to the class of pushdown automata where the stack alphabet contains one symbol. We present a specific method of approximating the largest bisimulation of a one-counter net based on single-periodic arithmetic and the notion of stratified bisimulation.     

Strategy logic

We introduce strategy logic, a logic that treats strategies in two-player games as explicit first-order objects. The explicit treatment of strategies allows us to specify properties of nonzero-sum games in a simple and natural way. We show that the one-alternation fragment of strategy logic is strong enough to express the existence of Nash equilibria and secure equilibria, and subsumes other logics that were introduced to reason about games, such as ATL, ATL¹, and game logic. We show that strategy logic is decidable, by constructing tree automata that recognize sets of strategies. While for the general logic, our decision procedure is nonelementary, for the simple fragment that is used above we show that the complexity is polynomial in the size of the game graph and optimal in the size of the formula (ranging from polynomial to 2EXPTIME depending on the form of the formula).     

Tree automata with equality constraints modulo equational theories

This paper presents new classes of tree automata combining automata with equality test and automata modulo equational theories. We believe that these classes have a good potential for application in e.g. software verification. These tree automata are obtained by extending the standard Horn clause representations with equational conditions and rewrite systems. We show in particular that a generalized membership problem (extending the emptiness problem) is decidable by proving that the saturation of tree automata presentations with suitable paramodulation strategies terminates. Alternatively our results can be viewed as new decidable classes of first-order formula.     

Deep pushdown automata

This paper introduces and discusses deep pushdown automata as a generalization of the classical pushdown automata. This generalization consists in allowing them to make expansions deeper in the pushdown. Based on the expansion depth, the present paper establishes an infinite hierarchy of language families that coincides with the hierarchy resulting from the n-limited state grammars, so the deep pushdown automata actually represent the automaton counterpart to these grammars. In its conclusion, this paper suggests some open problem areas.     

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.     

Teams of pushdown automata

We introduce team pushdown automata (PDAs) as a theoretical framework capable of modelling various communication and cooperation strategies in complex, distributed systems. Team PDAs are obtained by augmenting distributed PDAs with the notion of team cooperation or, alternatively, by augmenting team automata with pushdown memory. In a team PDA, several PDAs work as a team on the input word placed on a common one-way input tape. At any moment in time one team of PDAs, each with the same symbol on top of its stack, is active: each PDA in the active team replaces the topmost symbol of its stack and changes state, while the current input symbol is read from the input tape by a common reading head. The teams are formed according to the team cooperation strategy of the team PDA and may vary from one moment to the other. Based on the notion of competence, we introduce a variety of team cooperation strategies. If all stacks are empty when the input word has been completely read, then this word is part of the language accepted by the team PDA. Here we focus on the accepting capacity of team PDA.     

On The Space Complexity Of Turn Bounded Pushdown Automata

A pushdown automaton is said to make a turn at a given instant if it changes at that instant from stack increasing to stack decreasing. Let \hbox{NPDA-TURN}(\,f(n)) and \hbox{DPDA-TURN}(\,f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f v ( n ) turns for any input of length n . In this paper the following inclusions that express the space complexity of turn bounded pushdown automata are given: \hbox{DPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log f(n)\log n) , and \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf NSPACE} (\log f(n)\log n) . In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: \hbox{DPDA-TURN}(O(1))\subseteq {\bf DL} and \hbox{NPDA-TURN}(O(1))\subseteq {\bf NL} , from which two corollaries follow: one is that the class of metalinear context-free languages is complete for NL , and the other is that a more tight inclusion \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log n) cannot be derived unless {\bf DL}={\bf NL} , though \hbox{NPDA-TURN} (\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log^2n) holds.