scientific article; zbMATH DE number 3576701
From MaRDI portal
Publication:4146255
zbMath0369.68035MaRDI QIDQ4146255
Publication date: 1977
Full work available at URL: https://eudml.org/doc/92050
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10) Algorithms in computer science (68W99)
Related Items (6)
Refined simulation of multihead automata ⋮ Hierarchies of one-way multihead automata languages ⋮ Alternating multihead finite automata ⋮ Unnamed Item ⋮ On efficient recognition of transductions and relations ⋮ Some undecidable problems for parallel communicating finite automata systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On tape-bounded complexity classes and multihead finite automata
- An observation on time-storage trade off
- General context-free recognition in less than cubic time
- Space-bounded reducibility among combinatorial problems
- Translational lemmas, polynomial time, and \((\log n)^j\)-space
- Comparing complexity classes
- Time bounded random access machines
- On the computational power of pushdown automata
- On non-determinacy in simple computing devices
- Pushdown automata with counters
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- On two-way multihead automata
- The Hardest Context-Free Language
- A note on computing time for recognition of languages generated by linear grammars
- Multi-tape and multi-head pushdown automata
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Time and tape complexity of pushdown automaton languages
This page was built for publication:
