Site-Directed Insertion: Decision Problems, Maximality and Minimality - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

Site-Directed Insertion: Decision Problems, Maximality and Minimality

(1) , (1) , (2) , (2)
Da-Jung Cho
  • Function : Author
  • PersonId : 1038037
Yo-Sub Han
  • Function : Author
  • PersonId : 1024595
Kai Salomaa
  • Function : Author
  • PersonId : 1022715
Taylor J. Smith
  • Function : Author
  • PersonId : 1038038


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.
Fichier principal
Vignette du fichier
470153_1_En_5_Chapter.pdf (376.8 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01905635 , version 1 (26-10-2018)


Attribution - CC BY 4.0



Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor J. 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⟩
49 View
11 Download



Gmail Facebook Twitter LinkedIn More