Skip to Main content Skip to Navigation
Conference papers

Site-Directed Insertion: Decision Problems, Maximality and Minimality

Da-Jung Cho 1, 2 Yo-Sub Han 1 Kai Salomaa 3 Taylor Smith 3
2 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
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 we show that one variable equations involving site-directed insertion and regular constants can be solved. We consider also maximal and minimal variants of the site-directed insertion operation.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01937654
Contributor : Da-Jung Cho <>
Submitted on : Wednesday, November 28, 2018 - 11:11:49 AM
Last modification on : Monday, February 15, 2021 - 10:50:04 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01937654, version 1

Citation

Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor Smith. Site-Directed Insertion: Decision Problems, Maximality and Minimality. 20th International Conference on Descriptional Complexity of Formal Systems, Jul 2018, Halifax, Canada. ⟨hal-01937654⟩

Share

Metrics

Record views

70

Files downloads

407