Some modifications of auxiliary pushdown automata

DOI10.1051/ITA/1991250605451MaRDI QIDQ3485868zbMATH OpenOpenAlexFDO

Authors Gerhard Buntrock, Clemens Lautemann, Till Mossakowski, Frank Drewes

Publication date 1991

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92404

zbMATH Keywords

auxiliary pushdown automataLBA problemlogarithmic space

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Variations on pushdown machines (Detailed Abstract)
• Reversals and alternation
• Properties of probabilistic pushdown automata
• Alternating Pushdown and Stack Automata
• Properties of probabilistic pushdown automata

Cites work

• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Classes of languages and linear-bounded automata
• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3471606 (Why is no real title available?)
• scientific article; zbMATH DE number 3530982 (Why is no real title available?)
• scientific article; zbMATH DE number 3560742 (Why is no real title available?)
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Nondeterministic Space is Closed under Complementation
• On the Tape Complexity of Deterministic Context-Free Languages
• The complexity of theorem-proving procedures
• The method of forced enumeration for nondeterministic automata

Cited in

(3)

• scientific article; zbMATH DE number 4131657 (Why is no real title available?)
• scientific article; zbMATH DE number 4092805 (Why is no real title available?)
• scientific article; zbMATH DE number 2150283 (Why is no real title available?)

This page was built for publication: Some modifications of auxiliary pushdown automata

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