1 citations · 4 across the 10 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.FL2020
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…
cs.FL2020
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…
cs.FL2020★ 1 cited
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…