Abstract
It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound (m+2)·2mn-m-1·3m and find a lower bound for an asymp-totically tight bound. We also present the tight nondeterministic state complexity by a fooling set technique. The deterministic state complexity of insertion is 2Θ(mn) and the nondeterministic state complexity of insertion is precisely mn+2m, where m and n are the size of input finite automata. We also consider the state complexity of insertion in the case where the inserted language is bifix-free or non-returning.
| Original language | English |
|---|---|
| Pages (from-to) | 863-878 |
| Number of pages | 16 |
| Journal | International Journal of Foundations of Computer Science |
| Volume | 27 |
| Issue number | 7 |
| DOIs | |
| Publication status | Published - 2016 Nov 1 |
Bibliographical note
Funding Information:Han and Ko were supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097), the Yonsei University Future- leading Research Initiative of 2015 and the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512), and Ng and Salomaa were sup- ported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
Publisher Copyright:
© 2016 World Scientific Publishing Company.
All Science Journal Classification (ASJC) codes
- Computer Science (miscellaneous)