Binary and circular automata having maximal state complexity for the set of synchronizing words

DOI10.1016/j.ic.2023.105076OpenAlexW4385407901MaRDI QIDQ6186314

Stefan Hoffmann

Publication date: 2 February 2024

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

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

zbMATH Keywords

synchronizationfinite automatonstate complexityset of synchronizing wordsbinary automatoncompletely reachable automaton

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Černý conjecture and 1-contracting automata
• Primitive digraphs with large exponents and slowly synchronizing automata
• A graph theoretic approach to automata minimality
• Extremal minimality conditions on automata
• The road coloring problem
• Synchronizing automata with a letter of deficiency 2
• Synchronization
• The state complexities of some basic operations on regular languages
• Černý's conjecture and the road colouring problem
• Sync-maximal permutation groups equal primitive permutation groups
• Reset complexity and completely reachable automata with simple idempotents
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Primitivity, uniform minimality, and state complexity of Boolean operations
• Between primitive and 2-transitive: synchronization and its friends
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Les automates circulaires biaisés vérifient la conjecture de Černý
• Semicomputable points in Euclidean spaces
• Reset Complexity of Ideal Languages Over a Binary Alphabet
• Completely distinguishable automata and the set of synchronizing words
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• Binary completely reachable automata

This page was built for publication: Binary and circular automata having maximal state complexity for the set of synchronizing words