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

DOI10.1016/J.IC.2023.105076MaRDI QIDQ6186314zbMATH OpenOpenAlexFDO

Authors 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

binary automatoncompletely reachable automatonfinite automatonset of synchronizing wordsstate complexitysynchronization

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A graph theoretic approach to automata minimality
• A note on homogeneous experiments with finite automata
• A survey on operational state complexity
• Between primitive and 2-transitive: synchronization and its friends
• Binary completely reachable automata
• Codes and automata.
• Completely distinguishable automata and the set of synchronizing words
• Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words
• Completely Reachable Automata: An Interplay Between Automata, Graphs, and Trees
• Extremal minimality conditions on automata
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3605922 (Why is no real title available?)
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• scientific article; zbMATH DE number 7152073 (Why is no real title available?)
• scientific article; zbMATH DE number 3266647 (Why is no real title available?)
• scientific article; zbMATH DE number 3354928 (Why is no real title available?)
• Les automates circulaires biaisés vérifient la conjecture de Černý
• Primitive digraphs with large exponents and slowly synchronizing automata
• Primitivity, uniform minimality, and state complexity of Boolean operations
• Reset complexity and completely reachable automata with simple idempotents
• Reset complexity of ideal languages over a binary alphabet
• Reset Sequences for Monotonic Automata
• Semicomputable points in Euclidean spaces
• State complexity of the set of synchronizing words for circular automata and automata over binary alphabets
• Sync-maximal permutation groups equal primitive permutation groups
• Synchronization
• Synchronizing Automata and the Černý Conjecture
• Synchronizing automata with a letter of deficiency 2
• The road coloring problem
• The state complexities of some basic operations on regular languages
• The Černý conjecture and 1-contracting automata
• Černý's conjecture and the road colouring problem

Cited in

(1)

• Completely distinguishable automata and the set of synchronizing words

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

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