8 citations · 16 across the 15 of their papers we have counts for
4 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…
A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen +1
We study the expressiveness and succinctness of history-deterministic pushdown automata (HD-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved…
A Ramsey Theorem for Finite Monoids
Ismaël Jecker
Repeated idempotent elements are commonly used to characterise iterable behaviours in abstract models of computation. Therefore, given a monoid , it is natural to ask how long a…