Relationships between pushdown automata with counters and complexity classes

DOI10.1007/BF01735143MaRDI QIDQ4118823zbMATH OpenOpenAlexFDO

Authors Burkhard Monien

Publication date 1975

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01735143

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• A note on computing time for recognition of languages generated by linear grammars
• A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars
• An efficient context-free parsing algorithm
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Multi-tape and multi-head pushdown automata
• On the Computational Complexity of Algorithms
• Pushdown automata with counters
• Recognition and parsing of context-free languages in time n3
• Time and tape complexity of pushdown automaton languages
• Two-way pushdown automata

Cited in

(1)

• Remarks on two-way automata with weak-counters

This page was built for publication: Relationships between pushdown automata with counters and complexity classes

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