Publication:4146255
From MaRDI portal
zbMath0369.68035MaRDI QIDQ4146255
Publication date: 1977
Full work available at URL: https://eudml.org/doc/92050
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
03D10: Turing machines and related notions
68W99: Algorithms in computer science
Related Items
On efficient recognition of transductions and relations, Hierarchies of one-way multihead automata languages, Alternating multihead finite automata, Refined simulation of multihead automata, Some undecidable problems for parallel communicating finite automata systems, Unnamed Item
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
