1 citations · 1 across the 2 of their papers we have counts for
7 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…
Decomposing Permutation Automata
Ismaël Jecker, Nicolas Mazzocchi, Petra Wolf
A deterministic finite automaton (DFA) is composite if its language can be decomposed into an intersection of languages of smaller DFAs. Otherwise, A is prime. This notion of prima…
Properties of Graphs Specified by a Regular Language
Volker Diekert, Henning Fernau, Petra Wolf
Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property . What happens if this question is modified i…
Synchronizing Deterministic Push-Down Automata Can Be Really Hard
Henning Fernau, Petra Wolf, Tomoyuki Yamakami
The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend…
Synchronization of Deterministic Visibly Push-Down Automata
Henning Fernau, Petra Wolf
We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a s…
Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
Petra Wolf, Henning Fernau
The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton M as input, whether the language L(M) accepted by M contains any positive instance of the…