Site-directed insertion: Language equations and decision problems

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.

Authors

• Da-Jung Cho
• Yo-Sub Han
• Kai Salomaa
• Taylor J. Smith

Keywords

• Finite automata
• Language operations
• Shuffle on trajectories
• Decidability
• State complexity