Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata

DOI10.1007/978-3-642-22256-6_22zbMath1297.68156OpenAlexW2145224012MaRDI QIDQ5200068

Pavel Martyugin

Publication date: 29 July 2011

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22256-6_22

zbMATH Keywords

computational complexityautomatasynchronizationreset words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (1)

Computing the shortest reset words of synchronizing automata

Cites Work

• Unnamed Item
• Synchronizing monotonic automata
• Synchronizing automata preserving a chain of partial orders
• Synchronizing finite automata on Eulerian digraphs.
• Approximating the minimum length of synchronizing words is hard
• Composition sequences for functions over a finite domain.
• Reset Sequences for Monotonic Automata
• The Complexity of Finding Reset Words in Finite Automata
• On two Combinatorial Problems Arising from Automata Theory

This page was built for publication: Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata