On the complexity of finite, pushdown, and stack automata

DOI10.1007/BF01683261zbMath0351.68016OpenAlexW1990893893MaRDI QIDQ4121398

Harry B. III Hunt

Publication date: 1976

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items

The emptiness problem for intersections of regular languages ⋮ Iterated stack automata and complexity classes ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Time and space complexity of inside-out macro languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Nonerasing stack automata
• Scattered context grammars
• Relationships between nondeterministic and deterministic tape complexities
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• On the complexity of finite, pushdown, and stack automata
• The Hardest Context-Free Language
• Two-Tape Simulation of Multitape Turing Machines
• Indexed Grammars—An Extension of Context-Free Grammars
• Programmed Grammars and Classes of Formal Languages
• Nested Stack Automata
• Mappings and grammars on trees
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On Languages Accepted in Polynomial Time
• A Note Concerning Nondeterministic Tape Complexities
• The complexity of theorem-proving procedures
• Time and tape complexity of pushdown automaton languages