Narrow Results

We study one-way nondeterministic pushdown automata ($\text{N}\text{P}\text{D}\text{A}$), optionally with reversal-bounded counters. Finite-turn pushdown automata are pushdown automata with a bound on the number of switches between pushing and popping. We give new characterizations for finite-turn pushdown automata, and for finite-turn pushdown automata augmented with reversal-bounded counters. The first is in terms of multi-tape nondeterministic finite automata ($\text{N}\text{F}\text{A}$), and the second is in terms of multi-tape $\text{N}\text{F}\text{A}$ with reversal-bounded counters. We then use the characterizations to determine the complexity of the languages defined by these automata. In particular, we show that languages accepted by finite-turn $\text{N}\text{P}\text{D}\text{A}$ augmented with reversal-bounded counters are in $\text{N}\text{L}\text{O}\text{G}$. For the non-finite-turn case, the languages are in $\text{D}\text{S}\text{P}\text{A}\text{C}\text{E}({log}^{2}n)$ and in $P$. We also look at the space complexity of languages accepted by two-way machines. In particular, we show that every language accepted by a two-way $\text{N}\text{P}\text{D}\text{A}$ with reversal-bounded counters that makes a polynomial (resp., exponential) number of input head reversals is in $\text{D}\text{S}\text{P}\text{A}\text{C}\text{E}({log}^{2}n)$ (resp., $\text{D}\text{S}\text{P}\text{A}\text{C}\text{E}(n^2)$). This remains true if the pushdown can flip its contents a bounded number of times.

We consider automata systems consisting of several pushdown automata working in parallel and communicating the contents of their stacks by request, using a communication strategy borrowed from grammar system theory. We investigate the computational power of these mechanisms. We prove that non-centralized parallel communicating pushdown automata systems with a bounded number of components, where each automaton is allowed to issue a query, are able to recognize all recursively enumerable languages. We also present homomorphical characterizations of the class of recursively enumerable languages for the centralized variants, where only a distinguished automaton issues queries. Moreover, we show that these centralized variants are at least as powerful as one-way multihead pushdown automata. Finally, some open problems and further directions of research are discussed.

The article surveys some decidability results concerning simplification problems for DPDAs on infinite words (ω-DPDAs). We summarize some recent results on the regularity problem, which asks for a given ω-DPDA, whether its language can also be accepted by a finite automaton. The results also give some insights on the equivalence problem for a subclass of ω-DPDA. Furthermore, we present some new results on the parity index problem for ω-DPDAs. For the specification of a parity condition, the states of the ω-DPDA are assigned priorities (natural numbers), and a run is accepting if the highest priority that appears infinitely often during a run is even. The basic simplification question asks whether one can determine the minimal number of priorities that are needed to accept the language of a given ω-DPDA. We provide some decidability results on variations of this question for some classes of ω-DPDAs.

We construct the representations of Cayley graphs of wreath products using finite automata, pushdown automata and nested stack automata. These representations are in accordance with the notion of Cayley automatic groups introduced by Kharlampovich, Khoussainov and Miasnikov and its extensions introduced by Elder and Taback. We obtain the upper and lower bounds for a length of an element of a wreath product in terms of the representations constructed.

We present several new results on minimal space requirements to recognize a nonregular language: (i) realtime nondeterministic Turing machines can recognize a nonregular unary language within weak log log n space, (ii) log log n is a tight space lower bound for accepting general nonregular languages on weak realtime pushdown automata, (iii) there exist unary nonregular languages accepted by realtime alternating one-counter automata within weak log n space, (iv) there exist nonregular languages accepted by two-way deterministic pushdown automata within strong log log n space, and, (v) there exist unary nonregular languages accepted by two-way one-counter automata using quantum and classical states with middle log n space and bounded error.

A language $L$ is said to be dense if every word in the universe is an infix of some word in $L$. This notion has been generalized from the infix operation to arbitrary word operations $\varrho$ in place of the infix operation ($\varrho$-dense, with infix-dense being the standard notion of dense). It is shown here that it is decidable, for a language $L$ accepted by a one-way nondeterministic reversal-bounded pushdown automaton, whether $L$ is infix-dense. However, it becomes undecidable for both deterministic pushdown automata (with no reversal-bound), and for nondeterministic one-counter automata. When examining suffix-density, it is undecidable for more restricted families such as deterministic one-counter automata that make three reversals on the counter, but it is decidable with less reversals. Other decidability results are also presented on dense languages, and contrasted with a marked version called $\varrho$-marked-density. Also, new languages are demonstrated to be outside various deterministic language families after applying different deletion operations from smaller families. Lastly, bounded-dense languages are defined and examined.

Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding grammars to deterministic finite automata is known. The same size gap is also known from constant-height pushdown automata and $1$-limited automata to deterministic finite automata. Constant-height pushdown automata and $1$-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Furthermore, a polynomial size simulation by $1$-limited automata is presented. However, the converse transformation is proved to cost exponential. Finally, a different simulation shows that also the conversion of deterministic constant-height pushdown automata into deterministic $1$-limited automata costs polynomial.

Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that for language families ${ℒ}$ that are semilinear full trios, the smallest full AFL containing ${ℒ}$ that is also closed under intersection with languages in $\mathrm{\text{NCM}}$ (where $\mathrm{\text{NCM}}$ is the family of languages accepted by $\mathrm{\text{NFA}}$s augmented with reversal-bounded counters), is also semilinear. If these closure properties are effective, this also immediately implies decidability of membership, emptiness, and infiniteness for these general families. From the general techniques, new grammar systems are given that are extensions of well-known families of semilinear full trios, whereby it is implied that these extensions must only describe semilinear languages. This also implies positive decidability properties for the new systems. Some characterizations of the new families are also given.

This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automaton (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves like a linear function, or it can not be bounded by any function of the length of the input word (and it is decidable which case occurs). However, this result does not hold for non-erasing stack automata; we provide an example where the space complexity grows proportionally to the square root of the length of the input. Furthermore, we study the complexity bounds of machines which accept a given language, and decidability of space complexity properties.

We describe a part of the stimulus sentences of a German language processing ERP experiment using a context-free grammar and represent different processing preferences by its unambiguous partitions. The processing is modeled by deterministic pushdown automata. Using a theorem proven by Moore, we map these automata onto discrete time dynamical systems acting at the unit square, where the processing preferences are represented by a control parameter. The actual states of the automata are rectangles lying in the unit square that can be interpreted as cylinder sets in the context of symbolic dynamics theory. We show that applying a wrong processing preference to a certain input string leads to an unwanted invariant set in the parsers dynamics. Then, syntactic reanalysis and repair can be modeled by a switching of the control parameter — in analogy to phase transitions observed in brain dynamics. We argue that ERP components are indicators of these bifurcations and propose an ERP-like measure of the parsing model.

Several methods have been developed for identifying more or less complex RNA structures in a genome. All these methods are based on the search for conserved primary and secondary sub-structures. In this paper, we present a simple formal representation of a helix, which is a combination of sequence and folding constraints, as a constrained regular expression. This representation allows us to develop a well-founded algorithm that searches for all approximate matches of a helix in a genome. The algorithm is based on an alignment graph constructed from several copies of a pushdown automaton, arranged one on top of another. This is a first attempt to take advantage of the possibilities of pushdown automata in the context of approximate matching. The worst time complexity is O(krpn), where k is the error threshold, n the size of the genome, p the size of the secondary expression, and r its number of union symbols. We then extend the algorithm to search for pseudo-knots and secondary structures containing an arbitrary number of helices.

As special cases of deep pushdown automata, we discuss finitely expandable deep pushdown automata that always contain a bounded number of non-input symbols in their pushdown stores. Based on these automata, it establishes an infinite hierarchy of language families that coincides with the hierarchy resulting from matrix grammars of finite index. Thus finitely expandable deep pushdown automata can are an automaton counterpart to these grammars. It also follows that deleting transitions do not add more power to finitely expandable deep pushdown automata. In a final section, we suggest some open problems.