135 citations · 302 across the 18 of their papers we have counts for
Showing cs.FLShow all
2 papers · 1 filter
cs.FL2017★ 1 cited
Universality of Confluent, Self-Loop Deterministic Partially Ordered NFAs is Hard
Tomáš Masopust, Markus Krötzsch
An automaton is partially ordered if the only cycles in its transition diagram are self-loops. The expressivity of partially ordered NFAs (poNFAs) can be characterized by the Strau…
cs.FL2016★ 25 cited
Complexity of Universality and Related Problems for Partially Ordered NFAs
Markus Krötzsch, Tomáš Masopust, Michaël Thomazo
Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, that is, for which cycles occur only in the form o…