{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T04:12:40Z","timestamp":1749615160556,"version":"3.41.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319459936"},{"type":"electronic","value":"9783319459943"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-45994-3_13","type":"book-chapter","created":{"date-parts":[[2016,9,12]],"date-time":"2016-09-12T09:41:04Z","timestamp":1473673264000},"page":"177-191","source":"Crossref","is-referenced-by-count":1,"title":["Insertion-Deletion Systems over Relational Words"],"prefix":"10.1007","author":[{"given":"Igor","family":"Potapov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olena","family":"Prianychnykova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Verlan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,13]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Abdulla, P.A., Atig, M.F., Kara, A., Rezine, O.: Verification of dynamic register automata. In: FSTTCS 2014, pp. 653\u2013665","DOI":"10.1007\/978-3-319-26850-7_2"},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1016\/j.ejor.2003.09.034","volume":"164","author":"M Ayob","year":"2005","unstructured":"Ayob, M., Kendall, G.: A triple objective function with a Chebychev dynamic pick-and-place point specification approach to optimise the surface mount placement machine. Eur. J. Oper. Res. 164, 609\u2013626 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"13_CR3","unstructured":"Bouajjani, A., Dragoi, C., Jurski, Y., Sighireanu, M.: Rewriting systems over nested data words. In: MEMICS 2009"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-74240-1_1","volume-title":"Fundamentals of Computation Theory","author":"A Bouajjani","year":"2007","unstructured":"Bouajjani, A., Habermehl, P., Jurski, Y., Sighireanu, M.: Rewriting systems with data. In: Csuhaj-Varj\u00fa, E., \u00c9sik, Z. (eds.) FCT 2007. LNCS, vol. 4639, pp. 1\u201322. Springer, Heidelberg (2007)"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-319-11743-0_20","volume-title":"System Analysis and Modeling: Models and Reusability","author":"G Hackenberg","year":"2014","unstructured":"Hackenberg, G., Campetelli, A., Legat, C., Mund, J., Teufl, S., Vogel-Heuser, B.: Formal technical process specification and verification for automated production systems. In: Amyot, D., Fonseca i Casas, P., Mussbacher, G. (eds.) SAM 2014. LNCS, vol. 8769, pp. 287\u2013303. Springer, Heidelberg (2014)"},{"issue":"3","key":"13_CR6","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1142\/S0218216506004488","volume":"15","author":"C Hayashi","year":"2006","unstructured":"Hayashi, C.: A lower bound for the number of Reidemeister moves for unknotting. J. Knot Theor. Ramif. 15(3), 313\u2013325 (2006)","journal-title":"J. Knot Theor. Ramif."},{"issue":"1\u20132","key":"13_CR7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/j.tcs.2007.09.011","volume":"389","author":"V Halava","year":"2007","unstructured":"Halava, V., Harju, T., Karki, T.: Relational codes of words. Theoret. Comput. Sci. 389(1\u20132), 237\u2013249 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"13_CR8","doi-asserted-by":"crossref","first-page":"127","DOI":"10.3233\/FI-2015-1203","volume":"138","author":"S Ivanov","year":"2015","unstructured":"Ivanov, S., Verlan, S.: Random context and semi-conditional insertion-deletion systems. Fundamenta Informaticae. 138(1\u20132), 127\u2013144 (2015)","journal-title":"Fundamenta Informaticae."},{"issue":"2","key":"13_CR9","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0304-3975(94)90242-9","volume":"134","author":"M Kaminski","year":"1994","unstructured":"Kaminski, M., Francez, N.: Finite-memory automata. Theor. Comput. Sci. 134(2), 329\u2013363 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1007\/11493785_20","volume-title":"DNA Computing","author":"P Leupold","year":"2005","unstructured":"Leupold, P.: Partial Words for DNA coding. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 224\u2013234. Springer, Heidelberg (2005)"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Lisitsa, A., Potapov, I.: Temporal logic with predicate lambda-abstraction. In: TIME 2005, pp. 147\u2013155 (2005)","DOI":"10.1109\/TIME.2005.34"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Lisitsa, A., Potapov, I.: In time alone: on the computational power of querying the history. In: TIME 2006, pp. 42\u201349 (2006)","DOI":"10.1109\/TIME.2006.18"},{"issue":"2","key":"13_CR13","doi-asserted-by":"crossref","first-page":"395","DOI":"10.3233\/FI-2009-0049","volume":"91","author":"A Lisitsa","year":"2009","unstructured":"Lisitsa, A., Potapov, I.: On the computational power of querying the history. Fundamenta Informaticae 91(2), 395\u2013409 (2009)","journal-title":"Fundamenta Informaticae"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/978-3-642-21254-3_29","volume-title":"Language and Automata Theory and Applications","author":"A Lisitsa","year":"2011","unstructured":"Lisitsa, A., Potapov, I., Saleh, R.: Planarity of knots, register automata and LogSpace computability. In: Dediu, A.-H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 366\u2013377. Springer, Heidelberg (2011)"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/978-3-642-00982-2_43","volume-title":"Language and Automata Theory and Applications","author":"A Lisitsa","year":"2009","unstructured":"Lisitsa, A., Potapov, I., Saleh, R.: Automata on Gauss words. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 505\u2013517. Springer, Heidelberg (2009)"},{"key":"13_CR16","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1142\/9789814271059_0017","volume-title":"Modern Applications of Automata Theory","author":"A Manuel","year":"2012","unstructured":"Manuel, A., Ramanujam, R.: Automata over infinite alphabets. In: D\u2019Souza, D., Shankar, P. (eds.) Modern Applications of Automata Theory, pp. 529\u2013554. World Scientific, Singapore (2012)"},{"issue":"2","key":"13_CR17","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.tcs.2004.06.031","volume":"330","author":"M Margenstern","year":"2005","unstructured":"Margenstern, M., Paun, G., Rogozhin, Y., Verlan, S.: Context-free insertion-deletion systems. Theor. Comput. Sci. 330(2), 339\u2013348 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Palem, K.: Non-standard stringology: algorithms and complexity. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 770\u2013779. ACM, New York (1994)","DOI":"10.1145\/195058.195457"},{"issue":"3","key":"13_CR19","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1145\/1013560.1013562","volume":"5","author":"F Neven","year":"2004","unstructured":"Neven, F., Schwentick, T., Vianu, V.: Finite state machines for strings over infinite alphabets. ACM Trans. Comput. Log. 5(3), 403\u2013435 (2004)","journal-title":"ACM Trans. Comput. Log."},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-48523-6_9","volume-title":"Automata, Languages and Programming","author":"G Rozenberg","year":"1999","unstructured":"Rozenberg, G., Salomaa, A.: Dna computing: new ideas and paradigms. In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 106\u2013118. Springer, Heidelberg (1999)"},{"key":"13_CR21","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.tcs.2012.07.002","volume":"456","author":"I Petre","year":"2012","unstructured":"Petre, I., Verlan, S.: Matrix insertion-deletion systems. Theor. Comput. Sci. 456, 80\u201388 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR22","unstructured":"Potapov, I.: Composition problems for braids. In: Leibniz International Proceedings in Informatics, LIPIcs, FSTTCS 2013, vol. 24, pp. 175\u2013187. Leibniz-Zent. Inform (2013)"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Saleh, R.: On the length of knot transformations via Reidemeister moves I, II. In: RP 2012, pp. 121\u2013136","DOI":"10.1007\/978-3-642-33512-9_11"},{"key":"13_CR24","unstructured":"Saleh, R.: Computational aspects of knots and knot transformations. Ph.D. thesis, University of Liverpool (2011)"},{"key":"13_CR25","doi-asserted-by":"crossref","DOI":"10.1142\/3303","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformation: Volume 1 i-xv","author":"G Rozenberg","year":"1997","unstructured":"Rozenberg, G.: Handbook of Graph Grammars and Computing by Graph Transformation: Volume 1 i-xv. World Scientific, Singapore (1997)"},{"key":"13_CR26","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformation: Volume 2 i-xix","author":"H Ehrig","year":"1997","unstructured":"Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G.: Handbook of Graph Grammars and Computing by Graph Transformation: Volume 2 i-xix. World Scientific, Singapore (1997)"},{"key":"13_CR27","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformation: volume 3 i-xiii","author":"H Ehrig","year":"1997","unstructured":"Ehrig, H., Kreowski, H.-J., Montanari, U., Rozenberg, G.: Handbook of Graph Grammars and Computing by Graph Transformation: volume 3 i-xiii. World Scientific, Singapore (1997)"},{"key":"13_CR28","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/BF02952507","volume":"5","author":"K Reidemeister","year":"1926","unstructured":"Reidemeister, K.: Elementare Berndang der Knotentheorie. Abh. Math. Sem. Univ. Hamburg 5, 24\u201332 (1926)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"13_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/11874683_3","volume-title":"Computer Science Logic","author":"L Segoufin","year":"2006","unstructured":"Segoufin, L.: Automata and logics for words and trees over an infinite alphabet. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol. 4207, pp. 41\u201357. Springer, Heidelberg (2006)"},{"issue":"2","key":"13_CR30","first-page":"210","volume":"18","author":"S Verlan","year":"2010","unstructured":"Verlan, S.: Recent developments on insertion-deletion systems. Comput. Sci. J. Moldova 18(2), 210\u2013245 (2010)","journal-title":"Comput. Sci. J. Moldova"},{"key":"13_CR31","unstructured":"Vogel-Heuser, B., Legat, C., Folmer, J., Feldmann, S.: Researching evolution in industrial plant automation: Scenarios and documentation of the pick and place unit. Technical report TUM-AIS-TR-01-14-02, Institute of Automation and Information Systems, Technische Universitat Munchen (2014)"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45994-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T18:11:24Z","timestamp":1749579084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-45994-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319459936","9783319459943"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45994-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}