Site-Directed Insertion: Decision Problems, Maximality and Minimality

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905635
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:31 AM
Last modification on : Friday, October 26, 2018 - 8:05:07 AM
Long-term archiving on : Sunday, January 27, 2019 - 1:04:27 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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 (DCFS), Jul 2018, Halifax, NS, Canada. pp.49-61, ⟨10.1007/978-3-319-94631-3_5⟩. ⟨hal-01905635⟩

Share

Metrics

Record views

60