Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal

DOI10.1016/J.IPL.2010.03.008MaRDI QIDQ656586zbMATHOpenAlexFDO

Authors Marcin Balcerzak, Damian Niwiński

Publication date 18 January 2012

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

Full work available at URL https://doi.org/10.1016/j.ipl.2010.03.008

zbMATH Keywords

formal languagesregular languagesbounded number of reversalstwo-way finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2038729 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• Fooling a two-way nondeterministic multihead automaton with reversal number restriction
• Lower bounds on the size of sweeping automata
• Nondeterminism and the size of two way finite automata

Cited in

(1)

• scientific article; zbMATH DE number 3976379 (Why is no real title available?)

This page was built for publication: Two-way deterministic automata with two reversals are exponentially more succinct than with one reversal

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