Synchronizing automata with finitely many minimal synchronizing words

DOI10.1016/j.ic.2010.11.020zbMath1221.68141OpenAlexW2021874509MaRDI QIDQ553327

Elena V. Pribavkina, Emanuele Rodaro

Publication date: 27 July 2011

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

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

zbMATH Keywords

synchronizing automataco-NP-hard problemsminimal synchronizing words

Mathematics Subject Classification ID

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

Related Items (9)

Composition Sequences and Synchronizing Automata ⋮ Strongly connected synchronizing automata and the language of minimal reset words ⋮ STATE COMPLEXITY OF CODE OPERATORS ⋮ 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 ⋮ Semisimple Synchronizing Automata and the Wedderburn-Artin Theory ⋮ Recognizing Synchronizing Automata with Finitely Many Minimal Synchronizing Words is PSPACE-Complete ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems

Cites Work

• Resetting words for decidable automata
• Model-based testing of reactive systems. Advanced lectures.
• WORDS GUARANTEEING MINIMUM IMAGE
• Synchronizing Automata and the Černý Conjecture
• The Theory of Definite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Synchronizing automata with finitely many minimal synchronizing words