6 citations · 20 across the 20 of their papers we have counts for
23 papers
Sync-Maximal Permutation Groups Equal Primitive Permutation Groups
Stefan Hoffmann
The set of synchronizing words of a given -state automaton forms a regular language recognizable by an automaton with states. The size of a recognizing automaton for t…
State Complexity Investigations on Commutative Languages -- The Upward and Downward Closure, Commutative Aperiodic and Commutative Group Languages
Stefan Hoffmann
We investigate the state complexity of the upward and downward closure and interior operations on commutative regular languages. Then, we systematically study the state complexity…
Commutative Regular Languages with Product-Form Minimal Automata
Stefan Hoffmann
We introduce a subclass of the commutative regular languages that is characterized by the property that the state set of the minimal deterministic automaton can be written as a cer…
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann +4
In the Intersection Non-Emptiness problem, we are given a list of finite automata over a common alphabet as input, and the goal is to determine whether some…
Constrained Synchronization for Commutative Automata and Automata with Simple Idempotents
Stefan Hoffmann
For general input automata, there exist regular constraint languages such that asking if a given input automaton admits a synchronizing word in the constraint language is PSPACE-co…
The n-ary Initial Literal and Literal Shuffle
Stefan Hoffmann
The literal and the initial literal shuffle have been introduced to model the behavior of two synchronized processes. However, it is not possible to describe the synchronization of…