State Complexity of Basic Operations on Non-Returning Regular Languages

Article type: Research Article

Authors: Eom, Hae-Sung^a | Han, Yo-Sub^{a; *} | Jirásková, Galina^b

Affiliations: [a] Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea. {haesung, emmous}@cs.yonsei.ac.kr | [b] Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia. jiraskov@saske.sk

Correspondence: [*] Address for correspondence: Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Republic of Korea.

Abstract: 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, reverse, 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. In the case of catenation and reversal, we define witness languages over a ternary alphabet. Then we provide lower bounds for a binary alphabet. For every operation, we also study the unary case.

Keywords: Finite automata, non-returning regular languages, basic operations, state complexity

DOI: 10.3233/FI-2016-1326

Journal: Fundamenta Informaticae, vol. 144, no. 2, pp. 161-182, 2016