Shrinking alternating two-pushdown automata

Friedrich Otto; Etsuro Moriya

Shrinking alternating two-pushdown automata

Friedrich Otto^*, Etsuro Moriya

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.

Original language	English
Pages (from-to)	959-966
Number of pages	8
Journal	IEICE Transactions on Information and Systems
Volume	E87-D
Issue number	4
Publication status	Published - 2004 Apr

Keywords

Alternating
PSPACE-complete
Shrinking
Two-pushdown automaton

ASJC Scopus subject areas

Information Systems
Computer Graphics and Computer-Aided Design
Software

Cite this

@article{64c13382fe1d48c39ad6a59b19a1b33f,

title = "Shrinking alternating two-pushdown automata",

abstract = "The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.",

keywords = "Alternating, PSPACE-complete, Shrinking, Two-pushdown automaton",

author = "Friedrich Otto and Etsuro Moriya",

year = "2004",

month = apr,

language = "English",

volume = "E87-D",

pages = "959--966",

journal = "IEICE Transactions on Information and Systems",

issn = "0916-8532",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "4",

}

TY - JOUR

T1 - Shrinking alternating two-pushdown automata

AU - Otto, Friedrich

AU - Moriya, Etsuro

PY - 2004/4

Y1 - 2004/4

N2 - The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.

AB - The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.

KW - Alternating

KW - PSPACE-complete

KW - Shrinking

KW - Two-pushdown automaton

UR - http://www.scopus.com/inward/record.url?scp=2342454965&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2342454965&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:2342454965

SN - 0916-8532

VL - E87-D

SP - 959

EP - 966

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 4

ER -

Shrinking alternating two-pushdown automata

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this