@article{doi:10.1142/S012905411842008X,
    Abstract = {A nondeterministic finite automaton is unambiguous if it has at most one accepting computation on every input string. We investigate the state complexity of basic regular operations on languages represented by unambiguous finite automata. We get tight upper bounds for reversal (n), intersection (mn), left and right quotients (2n − 1), positive closure (3 42n − 1), star (3 42n), shuffle (2mn − 1), and concatenation (3 42m+n − 1). To prove tightness, we use a binary alphabet for intersection and left and right quotients, a ternary alphabet for star and positive closure, a five-letter alphabet for shuffle, and a seven-letter alphabet for concatenation. For complementation, we reduce the trivial upper bound 2n to 20.7856n+log n. We also get some partial results for union and square.},
    Author = {Jir{\'a}sek, Jozef and Jir{\'a}skov{\'a}, Galina and {\v S}ebej, Juraj},
    EPrint = {https://doi.org/10.1142/S012905411842008X},
    File = {Operations on Unambiguous Finite Automata - ufa.pdf},
    Journal = {International Journal of Foundations of Computer Science},
    Number = {05},
    Pages = {861-876},
    Title = {Operations on Unambiguous Finite Automata},
    URL = {https://doi.org/10.1142/S012905411842008X},
    Volume = {29},
    Year = {2018},
    bdsk-url-1 = {https://doi.org/10.1142/S012905411842008X},
    date-added = {2021-05-18 13:21:55 +0200},
    date-modified = {2021-05-18 13:21:55 +0200},
    doi = {10.1142/S012905411842008X}
}

@article{doi:10.1142/S012905411842008X, Abstract = {A nondeterministic finite automaton is unambiguous if it has at most one accepting computation on every input string. We investigate the state complexity of basic regular operations on languages represented by unambiguous finite automata. We get tight upper bounds for reversal (n), intersection (mn), left and right quotients (2n − 1), positive closure (3 42n − 1), star (3 42n), shuffle (2mn − 1), and concatenation (3 42m+n − 1). To prove tightness, we use a binary alphabet for intersection and left and right quotients, a ternary alphabet for star and positive closure, a five-letter alphabet for shuffle, and a seven-letter alphabet for concatenation. For complementation, we reduce the trivial upper bound 2n to 20.7856n+log n. We also get some partial results for union and square.}, Author = {Jir{\'a}sek, Jozef and Jir{\'a}skov{\'a}, Galina and {\v S}ebej, Juraj}, EPrint = {https://doi.org/10.1142/S012905411842008X}, File = {Operations on Unambiguous Finite Automata - ufa.pdf}, Journal = {International Journal of Foundations of Computer Science}, Number = {05}, Pages = {861-876}, Title = {Operations on Unambiguous Finite Automata}, URL = {https://doi.org/10.1142/S012905411842008X}, Volume = {29}, Year = {2018}, bdsk-url-1 = {https://doi.org/10.1142/S012905411842008X}, date-added = {2021-05-18 13:21:55 +0200}, date-modified = {2021-05-18 13:21:55 +0200}, doi = {10.1142/S012905411842008X} }