2014/05/22 by Kristína Čevorová, Galina Jirásková, Peter Mlynárčik +2
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.151.14
published as EPTCS 151, 2014, pp. 201-215 · In Proceedings AFL 2014, arXiv:1405.5272
arxiv created 2014/05/22 · arxiv updated 2014/05/23
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.