Shrinking Alternating Two-Pushdown Automata(Automata and Formal Language Theory)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2004-04-01

著者

• Otto Friedrich

  Fachbereich Mathematik

• MORIYA Etsuro

  Informatik, Universitat Kassel

• MORIYA Etsuro

  Department of Mathematics, School of Education, Waseda University

• Moriya Etsuro

  Department Of Mathematics School Of Education Waseda University

• Otto Friedrich

  Fachbereich Mathematik/informatik Universitat Kassel

• Otto Friedrich

  Fachbereich Elektrotechnik [Schragstrich] Informatik, Universitat Kassel

関連論文

• Shrinking Alternating Two-Pushdown Automata(Automata and Formal Language Theory)
• Two Ways of Introducing Alternation into Context-Free Grammars and Pushdown Automata(Automata and Formal Language Theory)
• Alternating CFG の拡張について(計算機科学の理論とその応用)
• Stack Tree Automata and Their Relation to Context-Free Grammars with Memory
• Some additional remarks on grammatical characterizations of alternating PDAs (理論計算機科学の深化--新たな計算世界観を求めて RIMS研究集会報告集)

スポンサーリンク