Complexity of a problem concerning reset words for Eulerian binary automata

DOI10.1016/j.ic.2016.06.013zbMath1362.68159OpenAlexW2570335695MaRDI QIDQ515691

Vojtěch Vorel

Publication date: 16 March 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2016.06.013

Mathematics Subject Classification ID

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

Related Items (3)

Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• Complexity of problems concerning reset words for cyclic and Eulerian automata
• Exact synchronization for finite-state sources
• The Černý conjecture for one-cluster automata with prime length cycle
• Existence of constants in regular splicing languages
• On Two Algorithmic Problems about Synchronizing Automata
• Strong Inapproximability of the Shortest Reset Word
• Modifying the Upper Bound on the Length of Minimal Synchronizing Word
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• The Complexity of Finding Reset Words in Finite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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