Kristína Čevorová |
Galina Jirásková |
Peter Mlynárčik |
Matúš Palmovský |
Juraj Šebej |
We study the complexity of basic regular operations on languages represented by incomplete deterministic or nondeterministic automata, in which all states are final. Such languages are known to be prefix-closed. We get tight bounds on both incomplete and nondeterministic state complexity of complement, intersection, union, concatenation, star, and reversal on prefix-closed languages. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.151.14 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |