3 citations · 6 across the 8 of their papers we have counts for
5 papers · 1 filter
State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets
Stefan Hoffmann
Most slowly synchronizing automata over binary alphabets are circular, i.e., containing a letter permuting the states in a single cycle, and their set of synchronizing words has ma…
Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words
Stefan Hoffmann
We give a new characterization of primitive permutation groups tied to the notion of completely reachable automata. Also, we introduce sync-maximal permutation groups tied to the s…
Ideal Separation and General Theorems for Constrained Synchronization and their Application to Small Constraint Automata
Stefan Hoffmann
In the constrained synchronization problem we ask if a given automaton admits a synchronizing word coming from a fixed regular constraint language. We show that intersecting a give…
Computational Complexity of Synchronization under Regular Commutative Constraints
Stefan Hoffmann
Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages. Utilizing a vector representation o…
State Complexity Bounds for the Commutative Closure of Group Languages
Stefan Hoffmann
In this work we construct an automaton for the commutative closure of a given regular group language. The number of states of the resulting automaton is bounded by the number of st…