Nondeterministic State Complexity of Site-Directed Insertion
| Autor: | Lyon, Oliver A. S., Salomaa, Kai |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| DOI: | 10.25596/jalc-2022-187 |
| Popis: | Site-directed insertion (a. k. a. outfix-guided insertion) is a controlled insertion operation where an outfix of the inserted string has to match a substring of the target string. We show that if $L_1$ and $L_2$ have NFAs (nondeterministic finite automata) with $N$ and $M$ states, respectively, the site-directed insertion of $L_2$ into $L_1$ can be recognized by an NFA with $3NM$ states. This improves the known upper bound for nondeterministic state complexity by an additive factor of $2N$. As our main result we establish for the nondeterministic state complexity of site-directed insertion a lower bound $3NM - M$. Journal of Automata, Languages and Combinatorics, Volume 27, Numbers 1-3, 2022, 187-197 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|