Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete

DOI10.1007/978-3-642-21875-0_24zbMath1345.68164OpenAlexW143622594MaRDI QIDQ3091460

Elena V. Pribavkina, Emanuele Rodaro

Publication date: 9 September 2011

Published in: Models of Computation in Context (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21875-0_24

Mathematics Subject Classification ID

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

Related Items (4)

Strongly connected synchronizing automata and the language of minimal reset words ⋮ Ideal regular languages and strongly connected synchronizing automata ⋮ Representation of (Left) Ideal Regular Languages by Synchronizing Automata ⋮ Groups and semigroups defined by colorings of synchronizing automata

Cites Work

• Unnamed Item
• Synchronizing automata with finitely many minimal synchronizing words
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture

This page was built for publication: Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete