Complexity of a problem concerning reset words for Eulerian binary automata

DOI10.1007/978-3-319-04921-2_47zbMATH Open1362.68158arXiv1409.2003OpenAlexW2142966575MaRDI QIDQ5404945FDOQ5404945

Publication date: 31 March 2014

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Abstract: A word is called a reset word for a deterministic finite automaton if it maps all the states of the automaton to a unique state. Deciding about the existence of a reset word of a given maximum length for a given automaton is known to be an NP-complete problem. We prove that it remains NP-complete even if restricted to Eulerian automata with binary alphabets, as it has been conjectured by Martyugin (2011).

Full work available at URL: https://arxiv.org/abs/1409.2003

Recommendations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (6)

This page was built for publication: Complexity of a problem concerning reset words for Eulerian binary automata

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