Seminár z teoretickej informatiky - Galina Jirásková (25.11.2016)
v piatok 25.11.2016 o 11:30 hod. v miestnosti M/213
Prednášajúci: Galina Jirásková
Názov: Operations on Unambiguous Finite Automata
Termín: 25.11.2016, 11:30 hod., M/213
Abstrakt:
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.
Podľa článku: Jozef Jirásek Jr., Galina Jirásková and Juraj Šebej: Operations on unambiguous finite automata, DLT 2016.
web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php