{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T17:31:30Z","timestamp":1743096690621,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031332630"},{"type":"electronic","value":"9783031332647"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-33264-7_10","type":"book-chapter","created":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T08:03:26Z","timestamp":1684397006000},"page":"113-127","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Synchronization of\u00a0Parikh Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7866-075X","authenticated-orcid":false,"given":"Stefan","family":"Hoffmann","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,19]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (ed.) STOC 2004, pp. 202\u2013211. ACM (2004). https:\/\/doi.org\/10.1145\/1007352.1007390","DOI":"10.1145\/1007352.1007390"},{"key":"10_CR2","doi-asserted-by":"publisher","unstructured":"Babari, P., Quaas, K., Shirmohammadi, M.: Synchronizing data words for register automata. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) MFCS 2016. LIPIcs, vol. 58, pp. 15:1\u201315:15. Schloss Dagstuhl (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.15","DOI":"10.4230\/LIPIcs.MFCS.2016.15"},{"key":"10_CR3","doi-asserted-by":"publisher","unstructured":"Balasubramanian, A.R., Thejaswini, K.S.: Adaptive synchronisation of pushdown automata. In: Haddad, S., Varacca, D. (eds.) 32nd International Conference on Concurrency Theory, CONCUR 2021, 24\u201327 August 2021, Virtual Conference. LIPIcs, vol. 203, pp. 17:1\u201317:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2021.17","DOI":"10.4230\/LIPIcs.CONCUR.2021.17"},{"key":"10_CR4","doi-asserted-by":"publisher","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Affine Parikh automata. RAIRO Theor. Informatics Appl. 46(4), 511\u2013545 (2012). https:\/\/doi.org\/10.1051\/ita\/2012013","DOI":"10.1051\/ita\/2012013"},{"issue":"3","key":"10_CR5","first-page":"208","volume":"14","author":"J \u010cern\u00fd","year":"1964","unstructured":"\u010cern\u00fd, J.: Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatmi. Matematicko-fyzik\u00e1lny \u010dasopis 14(3), 208\u2013216 (1964)","journal-title":"Matematicko-fyzik\u00e1lny \u010dasopis"},{"key":"10_CR6","doi-asserted-by":"publisher","unstructured":"Chistikov, D., Haase, C.: The taming of the semi-linear set. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) ICALP 2016. LIPIcs, vol. 55, pp. 128:1\u2013128:13. Schloss Dagstuhl (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.128","DOI":"10.4230\/LIPIcs.ICALP.2016.128"},{"key":"10_CR7","doi-asserted-by":"publisher","unstructured":"Chistikov, D., Martyugin, P., Shirmohammadi, M.: Synchronizing automata over nested words. Journal of Automata, Languages, and Combinatorics 24(2\u20134), 219\u2013251 (2019). https:\/\/doi.org\/10.25596\/jalc-2019-219","DOI":"10.25596\/jalc-2019-219"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/3-540-54345-7_57","volume-title":"Mathematical Foundations of Computer Science 1991","author":"E Domenjoud","year":"1991","unstructured":"Domenjoud, E.: Solving systems of linear diophantine equations: an algebraic approach. In: Tarlecki, A. (ed.) MFCS 1991. LNCS, vol. 520, pp. 141\u2013150. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/3-540-54345-7_57"},{"key":"10_CR9","doi-asserted-by":"publisher","unstructured":"Doyen, L., Juhl, L., Larsen, K.G., Markey, N., Shirmohammadi, M.: Synchronizing words for weighted and timed automata. In: Raman, V., Suresh, S.P. (eds.) FSTTCS 2014. LIPIcs, vol. 29, pp. 121\u2013132. Schloss Dagstuhl (2014). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2014.121","DOI":"10.4230\/LIPIcs.FSTTCS.2014.121"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-22993-0_27","volume-title":"Mathematical Foundations of Computer Science 2011","author":"L Doyen","year":"2011","unstructured":"Doyen, L., Massart, T., Shirmohammadi, M.: Infinite synchronizing words for probabilistic automata. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 278\u2013289. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22993-0_27"},{"key":"10_CR11","doi-asserted-by":"publisher","unstructured":"Doyen, L., Massart, T., Shirmohammadi, M.: The complexity of synchronizing markov decision processes. J. Comput. Syst. Sci. 100, 96\u2013129 (2019). https:\/\/doi.org\/10.1016\/j.jcss.2018.09.004","DOI":"10.1016\/j.jcss.2018.09.004"},{"key":"10_CR12","doi-asserted-by":"publisher","unstructured":"Fernau, H., Gusev, V.V., Hoffmann, S., Holzer, M., Volkov, M.V., Wolf, P.: Computational complexity of synchronization under regular constraints. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) MFCS 2019. LIPIcs, vol. 138, pp. 63:1\u201363:14. Schloss Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2019.63","DOI":"10.4230\/LIPIcs.MFCS.2019.63"},{"key":"10_CR13","unstructured":"Fernau, H., Wolf, P.: Synchronization of deterministic visibly push-down automata. In: Saxena, N., Simon, S. (eds.) FSTTCS 2020. LIPIcs, vol. 182, pp. 45:1\u201345:15. Schloss Dagstuhl (2020)"},{"key":"10_CR14","doi-asserted-by":"publisher","unstructured":"Fernau, H., Wolf, P., Yamakami, T.: Synchronizing deterministic push-down automata can be really hard. In: Esparza, J., Kr\u00e1l\u2019, D. (eds.) MFCS 2020. LIPIcs, vol. 170, pp. 33:1\u201333:15. Schloss Dagstuhl (2020). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.33","DOI":"10.4230\/LIPIcs.MFCS.2020.33"},{"key":"10_CR15","doi-asserted-by":"publisher","unstructured":"Figueira, D., Libkin, L.: Path logics for querying graphs: combining expressiveness and efficiency. In: LICS 2015, pp. 329\u2013340. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/LICS.2015.39","DOI":"10.1109\/LICS.2015.39"},{"issue":"6","key":"10_CR16","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1142\/S0129054113400170","volume":"24","author":"FM Fominykh","year":"2013","unstructured":"Fominykh, F.M., Martyugin, P.V., Volkov, M.V.: P(l)aying for synchronization. Int. J. Found. Comput. Sci. 24(6), 765\u2013780 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"10_CR17","first-page":"333","volume":"113","author":"S Ginsburg","year":"1964","unstructured":"Ginsburg, S., Spanier, E.H.: Bounded ALGOL-like languages. Trans. Am. Math. Soc. 113(2), 333\u2013368 (1964)","journal-title":"Trans. Am. Math. Soc."},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, presburger formulas, and languages. Pacific J. Math. 16(2), 285\u2013296 (1966). pjm\/1102994974","DOI":"10.2140\/pjm.1966.16.285"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Haase, C.: A survival guide to Presburger arithmetic. ACM SIGLOG News 5(3), 67\u201382 (2018). https:\/\/dl.acm.org\/citation.cfm?id=3242964","DOI":"10.1145\/3242953.3242964"},{"key":"10_CR20","doi-asserted-by":"publisher","unstructured":"Hoffmann, S.: Constrained synchronization and commutativity. Theor. Comput. Sci. 890, 147\u2013170 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.08.030, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397521005077","DOI":"10.1016\/j.tcs.2021.08.030"},{"key":"10_CR21","doi-asserted-by":"publisher","unstructured":"Holzer, M., Jakobi, S.: On the computational complexity of problems related to distinguishability sets. Inf. Comput. 259(2), 225\u2013236 (2018). https:\/\/doi.org\/10.1016\/j.ic.2017.09.003","DOI":"10.1016\/j.ic.2017.09.003"},{"key":"10_CR22","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, Boton (1979)"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/3-540-10003-2_81","volume-title":"Automata, Languages and Programming","author":"T-D Huynh","year":"1980","unstructured":"Huynh, T.-D.: The complexity of semilinear sets. In: de Bakker, J., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 324\u2013337. Springer, Heidelberg (1980). https:\/\/doi.org\/10.1007\/3-540-10003-2_81"},{"issue":"6","key":"10_CR24","first-page":"291","volume":"18","author":"T Huynh","year":"1982","unstructured":"Huynh, T.: The complexity of semilinear sets. J. Inf. Process. Cybern. (now J. Automata, Lang. Comb.) 18(6), 291\u2013338 (1982)","journal-title":"J. Inf. Process. Cybern. (now J. Automata, Lang. Comb.)"},{"issue":"1","key":"10_CR25","first-page":"105","volume":"14","author":"B Imreh","year":"1999","unstructured":"Imreh, B., Steinby, M.: Directable nondeterministic automata. Acta Cybernetica 14(1), 105\u2013115 (1999)","journal-title":"Acta Cybernetica"},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1002\/sapm1970491101","volume":"49","author":"D Kfoury","year":"1970","unstructured":"Kfoury, D.: Synchronizing sequences for probabilistic automata. Stud. Appl. Math. 49, 101\u2013103 (1970)","journal-title":"Stud. Appl. Math."},{"key":"10_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/3-540-45061-0_54","volume-title":"Automata, Languages and Programming","author":"F Klaedtke","year":"2003","unstructured":"Klaedtke, F., Rue\u00df, H.: Monadic second-order logics with cardinalities. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 681\u2013696. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_54"},{"key":"10_CR28","unstructured":"(Lin), A.W.T.: Model Checking Infinite-State Systems: Generic and Specific Approaches. Ph.D. thesis, University of Edinburgh (2010)"},{"issue":"2","key":"10_CR29","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00224-013-9516-6","volume":"54","author":"P Martyugin","year":"2013","unstructured":"Martyugin, P.: Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Theor. Comput. Syst. 54(2), 293\u2013304 (2013). https:\/\/doi.org\/10.1007\/s00224-013-9516-6","journal-title":"Theor. Comput. Syst."},{"key":"10_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-53904-2_94","volume-title":"Rewriting Techniques and Applications","author":"L Pottier","year":"1991","unstructured":"Pottier, L.: Minimal solutions of linear diophantine systems\u202f: bounds and algorithms. In: Book, R.V. (ed.) RTA 1991. LNCS, vol. 488, pp. 162\u2013173. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/3-540-53904-2_94"},{"key":"10_CR31","doi-asserted-by":"publisher","unstructured":"Quaas, K., Shirmohammadi, M.: Synchronizing data words for register automata. ACM Trans. Comput. Logic 20(2), 11:1\u201311:27 (2019). https:\/\/doi.org\/10.1145\/3309760","DOI":"10.1145\/3309760"},{"key":"10_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/11498490_2","volume-title":"Model-Based Testing of Reactive Systems","author":"S Sandberg","year":"2005","unstructured":"Sandberg, S.: 1 homing and synchronizing sequences. In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5\u201333. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11498490_2"},{"key":"10_CR33","doi-asserted-by":"publisher","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970). https:\/\/doi.org\/10.1016\/S0022-0000(70)80006-X","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"Volkov, M.V., Kari, J.: \u010cern\u00fd\u2019s conjecture and the road colouring problem. In: Pin, J.\u00c9. (ed.) Handbook of Automata Theory, vol. I, pp. 525\u2013565. European Mathematical Society Publishing House (2021)","DOI":"10.4171\/Automata-1\/15"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-33264-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T08:04:49Z","timestamp":1684397089000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-33264-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031332630","9783031332647"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-33264-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"19 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ume\u00e5","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sweden","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dltwords2023.cs.umu.se\/dlt","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"19","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4- Invited papers and 32 submissions (31 regular ones and one invited)","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}