Tight hierarchy of data-independent multi-head automata

DOI10.1016/J.JCSS.2020.06.005MaRDI QIDQ2194865zbMATH OpenOpenAlexFDO

Authors Pavol Ďuriš, Rastislav Královič, Dana Pardubská

Publication date 7 September 2020

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2020.06.005

zbMATH Keywords

data-independent automatahierarchymulti-head automataoblivious automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1361488
• Head and state hierarchies for unary multi-head finite automata
• scientific article; zbMATH DE number 3911746
• Multi-head finite automata: Data-independent versus data-dependent computations
• Hierarchies of one-way multihead automata languages

Cites work

• k + 1 Heads Are Better than k
• Bounded-reversal multihead finite automata languages
• Complexity of multi-head finite automata: origins and directions
• Hierarchies of one-way multihead automata languages
• scientific article; zbMATH DE number 6515829 (Why is no real title available?)
• scientific article; zbMATH DE number 3690693 (Why is no real title available?)
• scientific article; zbMATH DE number 3471609 (Why is no real title available?)
• scientific article; zbMATH DE number 1222567 (Why is no real title available?)
• Multi-head finite automata: Data-independent versus data-dependent computations
• On Multi-Head Finite Automata
• On non-determinacy in simple computing devices
• On tape-bounded complexity classes and multihead finite automata
• Relations Among Complexity Measures

Cited in

(2)

• Multi-head finite automata: Data-independent versus data-dependent computations
• scientific article; zbMATH DE number 1361488 (Why is no real title available?)

This page was built for publication: Tight hierarchy of data-independent multi-head automata

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