{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:03:50Z","timestamp":1743055430254,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030719944"},{"type":"electronic","value":"9783030719951"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"vor","delay-in-days":81,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The origin semantics for transducers was proposed in 2014, and it led to various characterizations and decidability results that are in contrast with the classical semantics. In this paper we add a further decidability result for characterizing transducers that are close to one-way transducers in the origin semantics. We show that it is decidable whether a non-deterministic two-way word transducer can be resynchronized by a bounded, regular resynchronizer into an origin-equivalent one-way transducer. The result is in contrast with the usual semantics, where it is undecidable to know if a non-deterministic two-way transducer is equivalent to some one-way transducer.<\/jats:p>","DOI":"10.1007\/978-3-030-71995-1_7","type":"book-chapter","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T17:03:39Z","timestamp":1616432619000},"page":"124-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["One-way Resynchronizability of Word Transducers"],"prefix":"10.1007","author":[{"given":"Sougata","family":"Bose","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. N.","family":"Krishna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anca","family":"Muscholl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriele","family":"Puppis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"unstructured":"Rajeev Alur and Pavel Cern\u00fd. Expressiveness of streaming string transducer. In IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201910), volume\u00a08 of LIPIcs, pages 1\u201312. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2010.","key":"7_CR1"},{"unstructured":"F\u00e9lix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. One-way definability of sweeping transducers. In IARCS Annual Conference on Foundation of Software Technologyand Theoretical Computer Science (FSTTCS\u201915), volume\u00a045 of LIPIcs, pages 178\u2013191. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2015.","key":"7_CR2"},{"unstructured":"F\u00e9lix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. One-way definability of two-way word transducers. Logical Methods in Computer Science, 14(4):1\u201354, 2018.","key":"7_CR3"},{"doi-asserted-by":"crossref","unstructured":"Mikolaj Boja\u0144czyk. Transducers with origin information. In International Colloquium on Automata, Languages and Programming (ICALP\u201914), number 8572 in LNCS, pages 26\u201337. Springer, 2014.","key":"7_CR4","DOI":"10.1007\/978-3-662-43951-7_3"},{"unstructured":"Mikolaj Boja\u0144czyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle. Which classes of origin graphs are generated by transducers? In International Colloquium on Automata, Languages and Programming (ICALP\u201917), volume\u00a080 of LIPIcs, pages 114:1\u2013114:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2017.","key":"7_CR5"},{"unstructured":"Sougata Bose, Shankara\u00a0Narayanan Krishna, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. On synthesis of resynchronizers for transducers. In International Symposium on Mathematical Foundations of Computer Science (MFCS\u201919), volume 138 of LIPIcs, pages 69:1\u201369:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2019.","key":"7_CR6"},{"unstructured":"Sougata Bose, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. Origin-equivalence of two-way word transducers is in PSPACE. In IARCS Annual Conference on Foundations of Software Technologyand Theoretical Computer Science (FSTTCS\u201918), volume 122 of LIPIcs, pages 1\u201318. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018.","key":"7_CR7"},{"doi-asserted-by":"crossref","unstructured":"Thomas Colcombet. Factorisation forests for infinite words. In Fundamentals of Computation Theory (FCT), volume 4639 of LNCS, pages 226\u2013237. Springer, 2007.","key":"7_CR8","DOI":"10.1007\/978-3-540-74240-1_20"},{"doi-asserted-by":"crossref","unstructured":"Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012.","key":"7_CR9","DOI":"10.1017\/CBO9780511977619"},{"doi-asserted-by":"crossref","unstructured":"Luc Dartois, Isma\u00ebl Jecker, and Pierre-Alain Reynier. Aperiodic string transducers. Int. J. Found. Comput. Sci., 29(5):801\u2013824, 2018.","key":"7_CR10","DOI":"10.1142\/S0129054118420054"},{"doi-asserted-by":"crossref","unstructured":"Joost Engelfriet and Hendrik\u00a0Jan Hoogeboom. MSO definable string transductions and two-way finite-statetransducers. ACM Trans. Comput. Log., 2(2):216\u2013254, 2001.","key":"7_CR11","DOI":"10.1145\/371316.371512"},{"unstructured":"Joost Engelfriet and Hendrik\u00a0Jan Hoogeboom. Finitary compositions of two-way finite-state transductions. Fundamenta Informaticae, 80:111\u2013123, 2007.","key":"7_CR12"},{"unstructured":"Emmanuel Filiot, Olivier Gauwin, and Nathan Lhote. Logical and algebraic characterizations of rational transductions. Logical Methods in Computer Science, 15(4), 2019.","key":"7_CR13"},{"doi-asserted-by":"crossref","unstructured":"Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Fr\u00e9d\u00e9ric Servais. From two-way to one-way finite state transducers. In ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201913), pages 468\u2013477, 2013.","key":"7_CR14","DOI":"10.1109\/LICS.2013.53"},{"unstructured":"Emmanuel Filiot, Isma\u00ebl Jecker, Christof L\u00f6ding, and Sarah Winter. On equivalence and uniformisation problems for finite transducers. In Proc. of nternational Colloquium on Automata, Languages, and Programming (ICALP\u201916), number 125 in LIPIcs, pages 1\u201314. Schloss Dagstuhl- Leibniz-Zentrum f\u00fcr Informatik, 2016.","key":"7_CR15"},{"unstructured":"Emmanuel Filiot, Shankara\u00a0Narayanan Krishna, and Ashutosh Trivedi. First-order definable string transformations. In IARCS Annual Conference on Foundations of Software Technologyand Theoretical Computer Science (FSTTCS\u201914), LIPIcs, pages 147\u2013159. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2014.","key":"7_CR16"},{"doi-asserted-by":"crossref","unstructured":"Emmanuel Filiot, Sebastian Maneth, Pierre-Alain Reynier, and Jean-Marc Talbot. Decision problems of tree transducers with origin. Inf. Comput., 261(Part):311\u2013335, 2018.","key":"7_CR17","DOI":"10.1016\/j.ic.2018.02.011"},{"doi-asserted-by":"crossref","unstructured":"T.\u00a0V. Griffiths. The unsolvability of the equivalence problem for lambda-free non-deterministic generalized machines. J. ACM, 15(3):409\u2013413, 1968.","key":"7_CR18","DOI":"10.1145\/321466.321473"},{"doi-asserted-by":"crossref","unstructured":"Oscar\u00a0H. Ibarra. The unsolvability of the equivalence problem for e-free NGSM\u2019s with unary input (output) alphabet and applications. SIAM J. of Comput., 7(4):524\u2013532, 1978.","key":"7_CR19","DOI":"10.1137\/0207042"},{"unstructured":"Ismael Jecker. Personal communication.","key":"7_CR20"},{"unstructured":"Denis Kuperberg and Jan Martens. Regular resynchronizability of origin transducers is undecidable. In International Symposium on Mathematical Foundations of Computer Science (MFCS\u201920), volume 170 of LIPIcs, pages 1\u201314. SchlossDagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020.","key":"7_CR21"},{"doi-asserted-by":"crossref","unstructured":"John\u00a0C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198\u2013200, 1959.","key":"7_CR22","DOI":"10.1147\/rd.32.0198"},{"doi-asserted-by":"crossref","unstructured":"Imre Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65\u201394, 1990.","key":"7_CR23","DOI":"10.1016\/0304-3975(90)90047-L"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-71995-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T04:34:24Z","timestamp":1671683664000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-71995-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030719944","9783030719951"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-71995-1_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"23 March 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FOSSACS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/fossacs","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":"88","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":"28","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":"32% - 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,2","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference changed to an online format due to the COVID-19 pandemic","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)"}}]}}