A Two-Way Automaton with Fewer States than Any Equivalent One-Way Automaton

DOI10.1109/T-C.1971.223273MaRDI QIDQ5622170zbMATH OpenOpenAlexFDO

Authors Bruce H. Barnes

Publication date 1971

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/t-c.1971.223273

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Cited in

(4)

• Finite automata and unary languages
• Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
• An asymmetric regular set
• Deterministic one-way simulation of two-way deterministic finite automata over small alphabets

This page was built for publication: A Two-Way Automaton with Fewer States than Any Equivalent One-Way Automaton

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