Descriptional complexity of two-way pushdown automata with restricted head reversals
type: Item
instance of: scholarly article
title: Descriptional complexity of two-way pushdown automata with restricted head reversals
zbMATH Open document ID: 1276.68094
author: Andreas Malcher
author: Carlo Mereghetti
author: Beatrice Palano
published in: Theoretical Computer Science
publication date: 2012-08-13T00:00:00Z
reviewed by: Giovanni Pighizzini
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6065035
zbMATH Keywords: two-way pushdown automata
zbMATH Keywords: bounded head reversals
zbMATH Keywords: bounded pushdown reversals
zbMATH Keywords: descriptional complexity
zbMATH Keywords: bounded languages
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.04.007
OpenAlex ID: W2031307533
cites work: Behaviours of Unary Quantum Automata
cites work: A note on bounded-reversal multipushdown machines
cites work: Finite automata and unary languages
cites work: More concise representation of regular languages by automata and regular expressions
cites work: Converting two-way nondeterministic unary automata into simpler automata.
cites work: Q5576254
cites work: Q5422234
cites work: Simple counter machines and number-theoretic problems
cites work: The complexity of the equivalence problem for two characterizations of Presburger sets
cites work: Q4198075
cites work: Q5583856
cites work: On the Succinctness of Different Representations of Languages
cites work: The Complexity of Regular(-Like) Expressions
cites work: Q3102144
cites work: Complexity of multi-head finite automata: origins and directions
cites work: Q5592246
cites work: A note on semilinear sets and bounded-reversal multihead pushdown automata
cites work: New Decidability Results Concerning Two-Way Counter Machines
cites work: Q5740422
cites work: Succinct representation of regular languages by Boolean automata
cites work: Q4465339
cites work: Q3517107
cites work: Descriptional Complexity of Bounded Context-Free Languages
cites work: A remark on middle space bounded alternating Turing machines
cites work: Optimal simulations between unary automata
cites work: Q4453217
cites work: Deterministic two-way one-head pushdown automata are very powerful
cites work: Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
cites work: Classes of Recursively Enumerable Sets and Their Decision Problems
cites work: Q4239067
cites work: Regularity and Related Problems for Deterministic Pushdown Automata
cites work: A note on the succinctness of descriptions of deterministic languages
DOI: 10.1016/J.TCS.2012.04.007
Recommended article: Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals
Recommended article: Q3700838
Recommended article: Descriptional Complexity of Input-Driven Pushdown Automata
Recommended article: On the determinacy problem for two-way pushdown automata
Recommended article: Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata
Recommended article: Descriptional complexity of unambiguous input-driven pushdown automata
Recommended article: Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata
Recommended article: Reversal on Regular Languages and Descriptional Complexity
Recommended article: Two-Way Reversible Multi-Head Finite Automata
review text: While in the case of finite automata, the possibility of moving the input head in both directions does not increase the recognition power, in the case of pushdown automata the models resulting by adding this capability, called two-way pushdown automata (2PDAs), are strictly more powerful than standard one-way pushdown automata (PDAs) that, as is well known, characterize the class of context-free languages. For instance, it is not difficult to write an algorithm which uses a deterministic 2PDA to recognize the language \(\{a^nb^nc^n\mid n\geq 0\}\), but, as is well known, such a language cannot be accepted by any PDA, even making use of nondeterminism. Actually, up to now, the computational power of 2PDAs has not been clearly identified. In particular, it is unknown whether these models are equivalent to linear bounded automata and whether the nondeterministic and the deterministic versions have the same computational power.NEWLINENEWLINEThe paper investigates, from a descriptional complexity point of view, 2PDAs which are allowed to make a constant number (i.e., not dependent on the input length) of input head reversals on each string. The authors show that under this restriction, 2PDAs have some interesting common properties with standard PDAs [the first author and the reviewer, Lect. Notes Comput. Sci. 4588, 312--323 (2007; Zbl 1202.68233); Inf. Comput. 227, 1--20 (2013; Zbl 1358.68173)]:NEWLINENEWLINE-- In the case of (letter- and word-) bounded languages, the number of pushdown turns can be reduced to a constant by exponentially increasing the size of the description.NEWLINENEWLINE-- If the restriction to bounded languages is dropped, then the size of the description of the resulting devices cannot be bounded by any recursive function.NEWLINENEWLINEFurther results are given, by restricting to deterministic 2PDAs. Not so many papers are devoted to the study of 2PDAs and, as already mentioned, fundamental questions about these devices are still open. This paper gi…
description: scientific article; zbMATH DE number 6065035