(k,l)-Unambiguity and Quasi-Deterministic Structures
Pascal Caron, Marianne Flouret, Ludovic Mignot · arXiv (Cornell University) · 2014
We focus on the family of $(k,l)$-unambiguous automata that encompasses the one of deterministic $k$-lookahead automata introduced by Han and Wood. We show that this family presents nice theoretical properties that allow us to compute quasi-deterministic structures. These structures can be used to solve the membership problem. We use some heuristics to reduce the size of these quasi-deterministic structures and show that they can be exponentially smaller than DFAs.