On The Space Complexity Of Turn Bounded Pushdown Automata

DOI10.1080/0020716022000005564MaRDI QIDQ4709850zbMATH OpenOpenAlexFDO

Authors Etsuro Moriya, Takemaru Tada

Publication date 2003

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/0020716022000005564

zbMATH Keywords

pushdown automatonspace complexityturn head reversal

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1439403
• Publication:3033319
• scientific article; zbMATH DE number 3481857
• Alternation for sublogarithmic space-bounded alternating pushdown automata
• scientific article; zbMATH DE number 3862469
• DNA Computing
• On the computational complexity of P automata
• A note on the space complexity of some decision problems for finite automata
• scientific article; zbMATH DE number 1759489
• On recursive and non-recursive trade-offs between finite-turn pushdown automata

Cites work

• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 522856 (Why is no real title available?)

Cited in

(8)

• Finite turns and the regular closure of linear context-free languages
• scientific article; zbMATH DE number 3858445 (Why is no real title available?)
• scientific article; zbMATH DE number 3862469 (Why is no real title available?)
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• scientific article; zbMATH DE number 1439403 (Why is no real title available?)
• Formal grammars for turn-bounded deterministic context-free languages
• Language acceptors with a pushdown: characterizations and complexity
• Techniques for showing the decidability of the boundedness problem of language acceptors

This page was built for publication: On The Space Complexity Of Turn Bounded Pushdown Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4709850)