ebooks logo journals logo reference works logo abstract databases logo
bullet  SIGN IN Register | Why Register? | Got a Voucher? alerts   marked lists   shopping cart 

informaworld

HOME   |   SEARCH   |   BROWSE
    Issues List       Latest Issue       Forthcoming Articles       Volume 80 Issue 3       Subscribe       Article       References       Related articles      
<< firstfirst   < prevprev   Table of contentstoc   next >next   last >>last
Publisher Logo Publication Cover
Search within this journal

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: 12 issues per year
Published in: journal International Journal of Computer Mathematics, Volume 80, Issue 3 March 2003 , pages 295 - 304
Number of References: 10
Formats available: PDF (English)
Article Requests: Order Reprints : Request Permissions
View Article: View Article (PDF) 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 \hboxlcubNPDA-TURNrcub(\,f(n)) and \hboxlcubDPDA-TURNrcub(\,f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f Sacute( 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: \hboxlcubDPDA-TURNrcub(\,f(n)) \subseteq lcub\bf DSPACErcub(\log f(n)\log n) , and \hboxlcubNPDA-TURNrcub(\,f(n)) \subseteq lcub\bf NSPACErcub (\log f(n)\log n) . In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: \hboxlcubDPDA-TURNrcub(O(1))\subseteq lcub\bf DLrcub and \hboxlcubNPDA-TURNrcub(O(1))\subseteq lcub\bf NLrcub , 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 \hboxlcubNPDA-TURNrcub(\,f(n)) \subseteq lcub\bf DSPACErcub(\log^2 f(n)\log n) cannot be derived unless lcub\bf DLrcub=lcub\bf NLrcub , though \hboxlcubNPDA-TURNrcub (\,f(n)) \subseteq lcub\bf DSPACErcub(\log^2 f(n)\log^2n) holds.
Keywords: Pushdown Automaton; Turn (head Reversal); Space Complexity
view references (10)
Bookmark with:
  • CiteULike
  • Del.icio.us
  • BibSonomy
  • Connotea
  • More bookmarks
Privacy Policy | Terms & Conditions | Accessibility | RSS
FAQs in: English . Français . Español . 中文(简体和繁體)
© 2009 Informa plc