ON THE SPACE COMPLEXITY OF TURN BOUNDED PUSHDOWN AUTOMATA
Authors:
Etsuro Moriya a;
Takemaru Tada b
| Affiliations: | a Department of Mathematics, School of Education, Waseda University, Shinjuku-ku, Tokyo 169-8050, Japan. |
| b Media Network Center, Waseda University, Shinjuku-ku, Tokyo 169-8050, Japan. |
DOI:
10.1080/0020716022000005564
Publication Frequency:
15 issues per year
Published in:
International Journal of Computer Mathematics,
Volume
80,
Issue
3
March
2003
, pages 295
- 304
Subjects:
Analysis - Mathematics;
Bioinformatics;
Computer Mathematics;
Discrete Mathematics;
Mathematical Finance;
Mathematical Logic;
Mathematical Numerical Analysis;
Systems & Computer Architecture;
Number of References: 10
Formats available:
PDF
(English)
View Article:
View Article (PDF)
Abstract
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 ( 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.
|
| Keywords: Pushdown Automaton; Turn (head Reversal); Space Complexity |
| view references (10) |

Download Citation

NPDA-TURN
(\,f(n)) and \hbox
( 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
CiteULike
Del.icio.us
BibSonomy
Connotea