Synchronizing automata with finitely many minimal synchronizing words

DOI10.1016/J.IC.2010.11.020MaRDI QIDQ553327zbMATH OpenOpenAlexFDO

Authors Elena 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

co-NP-hard problemsminimal synchronizing wordssynchronizing automata

Mathematics Subject Classification ID

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

Recommendations

• Finitely Generated Synchronizing Automata
• Synchronization of Some DFA
• Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
• 2-Synchronizing Words
• Modifying the upper bound on the length of minimal synchronizing word

Cites work

• scientific article; zbMATH DE number 3748943 (Why is no real title available?)
• scientific article; zbMATH DE number 1346363 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• Model-based testing of reactive systems. Advanced lectures.
• Resetting words for decidable automata
• Synchronizing Automata and the Černý Conjecture
• The Theory of Definite Automata
• WORDS GUARANTEEING MINIMUM IMAGE

Cited in

(24)

• Synchronizing finite automata with short reset words
• Strongly connected synchronizing automata and the language of minimal reset words
• Slowly synchronizing automata with fixed alphabet size
• Synchronizing words and monoid factorization: a parameterized perspective
• Mortality and synchronization of unambiguous finite automata
• Synchronizing automata over nested words
• Composition sequences and synchronizing automata
• State complexity of code operators
• Groups and semigroups defined by colorings of synchronizing automata.
• Infinite Synchronizing Words for Probabilistic Automata
• Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
• Representation of (left) ideal regular languages by synchronizing automata
• Ideal regular languages and strongly connected synchronizing automata
• 2-Synchronizing Words
• Finitely Generated Synchronizing Automata
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• Synchronized components of a subshift
• Synchronizing automata over nested words
• Extensions to minimal synchronizing words
• scientific article; zbMATH DE number 7152087 (Why is no real title available?)
• Synchronization of Some DFA
• Semisimple synchronizing automata and the Wedderburn-Artin theory
• Completely distinguishable automata and the set of synchronizing words
• Reset sink complexity of regular ideals

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

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