Publication:3885190

zbMath0442.68039MaRDI QIDQ3885190

Burkhard Monien

Publication date: 1980

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

zbMATH Keywords

hierarchy of languages; register machines; counter automata; one-letter alphabet; two-way multihead automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Multihead two-way probabilistic finite automata, Remarks on multihead pushdown automata and multihead stack automata, Finite automata and unary languages, Hierarchies of one-way multihead automata languages, Cyclic automata, k\(+1\) heads are better than k for PDAs, Alternating multihead finite automata, Tradeoffs for language recognition on alternating machines, Synchronized finite automata and 2DFA reductions, Amplification of slight probabilistic advantage at absolutely no cost in space, Multi-head finite automata: Data-independent versus data-dependent computations, On membrane hierarchy in P systems, On Bounded Symport/Antiport P Systems, On Stateless Multihead Finite Automata and Multihead Pushdown Automata, Simulations by Time-Bounded Counter Machines

Cites Work

• Unnamed Item
• Techniques for separating space complexity classes
• Relating refined space complexity classes
• Transformational methods and their application to complexity problems. Corrigenda
• On two-way multihead automata
• k + 1 Heads Are Better than k