Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Theoretical Computer Science - Galina Jirásková (25.11.2016)

Friday 25.11.2016 at 11:30, Lecture room M/213


23. 11. 2016 09.33 hod.
By: Rastislav Královič

Galina Jirásková:
Operations on Unambiguous Finite Automata


Abstract:
A nondeterministic finite automaton is unambiguous if it has at most one accepting computation on every input string. We investigate the complexity of basic regular operations on languages represented by unambiguous finite automata. We get tight upper bounds for intersection (mn),left and right quotients (2^n-1), positive closure ({3over 4}cdot2^n-1), star ({3over 4}cdot2^n), shuffle (2^{mn}-1), and concatenation ({3over 4}cdot2^{m+n}-1). We also get some partial results for union and complementation. The most interesting result of the paper is the upper bound O(2^{0.79n}) for complementation.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php