3 citations · 6 across the 8 of their papers we have counts for
13 papers · 1 filter
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…
Constrained Synchronization and Subset Synchronization Problems for Weakly Acyclic Automata
Stefan Hoffmann
We investigate the constrained synchronization problem for weakly acyclic, or partially ordered, input automata. We show that, for input automata of this type, the problem is alway…
State Complexity of Projection on Languages Recognized by Permutation Automata and Commuting Letters
Stefan Hoffmann
The projected language of a general deterministic automaton with states is recognizable by a deterministic automaton with states, where denotes the…
Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited
Henning Fernau, Stefan Hoffmann, Michael Wehar
The problem DFA-Intersection-Nonemptiness asks if a given number of deterministic automata accept a common word. In general, this problem is PSPACE-complete. Here, we investigate t…