On multi-head automata with restricted nondeterminism

DOI10.1016/J.IPL.2012.04.009MaRDI QIDQ436607zbMATHOpenAlexFDO

Authors Daniel Reidenbach, Markus L. Schmid

Publication date 25 July 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://dspace.lboro.ac.uk/2134/9847

zbMATH Keywords

formal languagesmulti-head automatarestricted nondeterminism

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Fooling a two-way nondeterministic multihead automaton with reversal number restriction
• Some characterizations of multihead finite automata
• scientific article; zbMATH DE number 4058871
• On stateless multihead automata: hierarchies and the emptiness problem
• On Stateless Multihead Automata: Hierarchies and the Emptiness Problem

Cites work

• scientific article; zbMATH DE number 2068877 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• Amounts of nondeterminism in finite automata
• Complementing deterministic tree-walking automata
• Complementing two-way finite automata
• Complexity of multi-head finite automata: origins and directions
• Halting space-bounded computations
• On Multi-Head Finite Automata
• On non-determinacy in simple computing devices
• On tape-bounded complexity classes and multihead finite automata
• Real-time computations with restricted nondeterminism

Cited in

(11)

• Multitape NFA: Weak Synchronization of the Input Heads
• Finite dP Automata versus Multi-head Finite Automata
• Complexity of multi-head finite automata: origins and directions
• scientific article; zbMATH DE number 1361488 (Why is no real title available?)
• On Models of a Nondeterministic Computation
• A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
• Multi-head finite automata: Data-independent versus data-dependent computations
• Some characterizations of multihead finite automata
• Self-verifying nondeterministic and Las Vegas multihead two dimensional finite automata
• On Synchronized Multitape and Multihead Automata
• scientific article; zbMATH DE number 4058871 (Why is no real title available?)

This page was built for publication: On multi-head automata with restricted nondeterminism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q436607)