zbMATH — the first resource for mathematics

\((k,l)\)-unambiguity and quasi-deterministic structures: an alternative for the determinization. (English) Zbl 1408.68089
Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 8th international conference, LATA 2014, Madrid, Spain, March 10–14, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8370, 260-272 (2014).
Summary: We focus on the family of \((k,l)\)-unambiguous automata that encompasses the one of deterministic \(k\)-lookahead automata introduced by Y.-S. Han and D. Wood [Inf. Comput. 206, No. 9–10, 1117–1125 (2008; Zbl 1154.68069)]. We show that this family presents nice theoretical properties that allow us to compute quasi-deterministic structures. These structures are smaller than DFAs and can be used to solve the membership problem faster than NFAs.
For the entire collection see [Zbl 1283.68032].

68Q45 Formal languages and automata
Full Text: DOI