TY - GEN
T1 - State complexity of basic operations on non-returning regular languages
AU - Eom, Hae Sung
AU - Han, Yo Sub
AU - Jirásková, Galina
PY - 2013
Y1 - 2013
N2 - We consider the state complexity of basic operations on non-returning regular languages. For a non-returning minimal DFA, the start state does not have any in-transitions. We establish the precise state complexity of four Boolean operations (union, intersection, difference, symmetric difference), catenation, reversal, and Kleene-star for non-returning regular languages. Our results are usually smaller than the state complexities for general regular languages and larger than the state complexities for suffix-free regular languages.
AB - We consider the state complexity of basic operations on non-returning regular languages. For a non-returning minimal DFA, the start state does not have any in-transitions. We establish the precise state complexity of four Boolean operations (union, intersection, difference, symmetric difference), catenation, reversal, and Kleene-star for non-returning regular languages. Our results are usually smaller than the state complexities for general regular languages and larger than the state complexities for suffix-free regular languages.
UR - http://www.scopus.com/inward/record.url?scp=84884478140&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884478140&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-39310-5_7
DO - 10.1007/978-3-642-39310-5_7
M3 - Conference contribution
AN - SCOPUS:84884478140
SN - 9783642393099
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 54
EP - 65
BT - Descriptional Complexity of Formal Systems - 15th International Workshop, DCFS 2013, Proceedings
T2 - 15th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2013
Y2 - 22 July 2013 through 25 July 2013
ER -