Site-directed insertion: Language equations and decision problems
Loading...
Authors
Cho, Da-Jung
Han, Yo-Sub
Salomaa, Kai
Smith, Taylor J.
Date
2019-05-23
Type
journal article
Language
Keyword
Decidability , Finite Automata , Language Operations , Shuffle on Trajectories , State Complexity
Alternative Title
Abstract
Site-directed insertion is an overlapping insertion operation that can be viewed as analogous to the overlap assembly or chop operations that concatenate strings by overlapping a suffix and a prefix of the argument strings. We consider decision problems and language equations involving site-directed insertion. By relying on the tools provided by semantic shuffle on trajectories (M. Domaratzki, Developments in Language Theory 2004) we show that one variable equations involving site-directed insertion and regular constants can be solved algorithmically. We consider also maximal and minimal variants of the site-directed insertion operation and the nondeterministic state complexity of site-directed insertion.
Description
The final publication is available at Elsevier via http://dx.doi.org/10.1016/j.tcs.2019.04.019 ©2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/
Citation
Cho, D.-J., Han, Y.-S., Salomaa, K., & Smith, T. J. (2019). Site-directed insertion: Language equations and decision problems. Theoretical Computer Science. doi:10.1016/j.tcs.2019.04.019
Publisher
Elsevier