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.
Cho and Han were supported by the Basic Science Research Program through NRF (2015R1D1A1A01060097) and the International Research & Development Program of NRF (2017K1A3A1A12024971). Salomaa and Smith were supported by Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Birget, J.C.: Intersection and union of regular languages and state complexity. Inf. Process. Lett. 43, 185–190 (1992)
Cho, D.-J., Han, Y.-S., Ng, T., Salomaa, K.: Outfix-guided insertion. Theor. Comput. Sci. 701, 70–84 (2017)
Csuhaj-Varju, E., Petre, I., Vaszil, G.: Self-assembly of string and languages. Theor. Comput. Sci. 374, 74–81 (2007)
Daley, M., Kari, L., Gloor, G., Siromoney, R.: Circular contextual insertions/deletions with applications to biomolecular computation. In: String Processing and Information Retrieval Symposium, pp. 47–54 (1999)
Domaratzki, M.: Semantic shuffle on and deletion along trajectories. In: Calude, C.S., Calude, E., Dinneen, M.J. (eds.) DLT 2004. LNCS, vol. 3340, pp. 163–174. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30550-7_14
Domaratzki, M.: Trajectory-based codes. Acta Inf. 40, 491–527 (2004)
Domaratzki, M., Rozenberg, G., Salomaa, K.: Interpreted trajectories. Fundamenta Informaticae 73, 81–97 (2006)
Enaganti, S., Kari, L., Kopecki, S.: A formal language model of DNA polymerase enzymatic activity. Fundamenta Informaticae 138, 179–192 (2015)
Enaganti, S., Ibarra, O., Kari, L., Kopecki, S.: On the overlap assembly of strings and languages. Nat. Comput. 16, 175–185 (2017)
Franco, G., Manca, V.: Algorithmic applications of XPCR. Nat. Comput. 10, 805–811 (2011)
Han, Y.-S., Ko, S.-K., Ng, T., Salomaa, K.: State complexity of insertion. Int. J. Found. Comput. Sci. 27, 863–878 (2016)
Holzer, M., Jakobi, S.: Descriptional complexity of chop operations on unary and finite languages. J. Autom. Lang. Comb. 17(2–4), 165–183 (2012)
Holzer, M., Jakobi, S., Kutrib, M.: The chop of languages. Theor. Comput. Sci. 682, 122–137 (2017)
Jürgensen, H., Konstantinidis, S.: Codes. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, Vol. 1, pp. 511–607. Springer, Heidelberg (1997). https://doi.org/10.1007/978-3-642-59136-5_8
Kari, L.: On language equations with invertible operations. Theor. Comput. Sci. 132, 129–150 (1994)
Kari, L., Thierrin, G.: Contextual insertions/deletions and computability. Inf. Comput. 131, 47–61 (1996)
Mateescu, A., Rozenberg, G., Salomaa, A.: Shuffle on trajectories: syntactic constraints. Theor. Comput. Sci. 197, 1–56 (1998)
Reikofski, J., Yao, B.Y.: Polymerase chain reaction (PCR) techniques for site-directed mutagenesis. Biotechnol. Adv. 10, 535–547 (1992)
Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 IFIP International Federation for Information Processing
About this paper
Cite this paper
Cho, DJ., Han, YS., Salomaa, K., Smith, T.J. (2018). Site-Directed Insertion: Decision Problems, Maximality and Minimality. In: Konstantinidis, S., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2018. Lecture Notes in Computer Science(), vol 10952. Springer, Cham. https://doi.org/10.1007/978-3-319-94631-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-94631-3_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-94630-6
Online ISBN: 978-3-319-94631-3
eBook Packages: Computer ScienceComputer Science (R0)