A note on multihead automata and context-sensitive languages

DOI10.1007/BF00289080zbMath0255.68021MaRDI QIDQ2558753

Walter J. Savitch

Publication date: 1973

Published in: Acta Informatica (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Expressing uniformity via oracles, On the computational complexity of membrane systems, Computing with cells: membrane systems – some complexity issues, Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties, On the descriptional power of heads, counters, and pebbles, On tape-bounded complexity classes and multihead finite automata, Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems, On Bounded Symport/Antiport P Systems, On determinism versus nondeterminism in P systems

Cites Work

• Unnamed Item
• Relationships between nondeterministic and deterministic tape complexities
• On non-determinacy in simple computing devices