{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T06:45:10Z","timestamp":1790232310136,"version":"4.1.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030452308","type":"print"},{"value":"9783030452315","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we investigate the problem of synthesizing computable functions of infinite words over an infinite alphabet (data <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-words). The notion of computability is defined through Turing machines with infinite inputs which can produce the corresponding infinite outputs in the limit. We use non-deterministic transducers equipped with registers, an extension of register automata with outputs, to specify functions. Such transducers may not define functions but more generally relations of data <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c9<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-words, and we show that it is PS<jats:sc>pace<\/jats:sc>-complete to test whether a given transducer defines a function. Then, given a function defined by some register transducer, we show that it is decidable (and again, PS<jats:sc>pace<\/jats:sc>-c) whether such function is computable. As for the known finite alphabet case, we show that computability and continuity coincide for functions defined by register transducers, and show how to decide continuity. We also define a subclass for which those problems are PT<jats:sc>ime<\/jats:sc>.<\/jats:p>","DOI":"10.1007\/978-3-030-45231-5_12","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"217-236","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Computability of Data Word Functions Defined by Transducers"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0318-1217","authenticated-orcid":false,"given":"L\u00e9o","family":"Exibard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emmanuel","family":"Filiot","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre-Alain","family":"Reynier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Berstel, J.: Transductions and Context-free Languages. Teubner Verlag (1979), http:\/\/www-igm.univ-mlv.fr\/~berstel\/LivreTransductions\/LivreTransductions.html","DOI":"10.1007\/978-3-663-09367-1"},{"key":"12_CR2","unstructured":"Carayol, A., L\u00f6ding, C.: Uniformization in Automata Theory. In: Proceedings of the 14th Congress of Logic, Methodology and Philosophy of Science, Nancy, July 19\u201326, 2011. pp. 153\u2013178. London: College Publications (2014), https:\/\/hal.archives-ouvertes.fr\/hal-01806575"},{"key":"12_CR3","unstructured":"Dave, V., Filiot, E., Krishna, S.N., Lhote, N.: Deciding the computability of regular functions over infinite words. CoRR abs\/1906.04199 (2019), http:\/\/arxiv.org\/abs\/1906.04199"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Demri, S., Lazic, R.: LTL with the freeze quantifier and register automata. ACM Trans. Comput. Log. 10(3), 16:1\u201316:30 (2009). https:\/\/doi.org\/10.1145\/1507244.1507246","DOI":"10.1145\/1507244.1507246"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Durand-Gasselin, A., Habermehl, P.: Regular transformations of data words through origin information. In: Foundations of Software Science and Computation Structures - 19th International Conference, FOSSACS 2016, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2016, Eindhoven, The Netherlands, April 2-8, 2016, Proceedings. pp. 285\u2013300 (2016). https:\/\/doi.org\/10.1007\/978-3-662-49630-5_17","DOI":"10.1007\/978-3-662-49630-5_17"},{"key":"12_CR6","doi-asserted-by":"publisher","unstructured":"Ehlers, R., Seshia, S.A., Kress-Gazit, H.: Synthesis with identifiers. In: Proceedings of the 15th International Conference on Verification, Model Checking, and Abstract Interpretation - Volume 8318. pp. 415\u2013433. VMCAI 2014 (2014). https:\/\/doi.org\/10.1007\/978-3-642-54013-4_23","DOI":"10.1007\/978-3-642-54013-4_23"},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Exibard, L., Filiot, E., Reynier, P.: Synthesis of data word transducers. In: 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands. pp. 24:1\u201324:15 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2019.24","DOI":"10.4230\/LIPIcs.CONCUR.2019.24"},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Figueira, D., Libkin, L.: Path logics for querying graphs: Combining expressiveness and efficiency. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015. pp. 329\u2013340 (2015). https:\/\/doi.org\/10.1109\/LICS.2015.39","DOI":"10.1109\/LICS.2015.39"},{"key":"12_CR9","doi-asserted-by":"publisher","unstructured":"Filiot, E., Jecker, I., L\u00f6ding, C., Winter, S.: On equivalence and uniformisation problems for finite transducers. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, Rome, Italy. pp. 125:1\u2013125:14 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.125","DOI":"10.4230\/LIPIcs.ICALP.2016.125"},{"key":"12_CR10","doi-asserted-by":"publisher","unstructured":"Filiot, E., Mazzocchi, N., Raskin, J.: A pattern logic for automata with outputs. In: Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings. pp. 304\u2013317 (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_25","DOI":"10.1007\/978-3-319-98654-8_25"},{"issue":"3","key":"12_CR11","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(86)90058-X","volume":"22","author":"F Gire","year":"1986","unstructured":"Gire, F.: Two decidability problems for infinite words. Inf. Process. Lett. 22(3), 135\u2013140 (1986). https:\/\/doi.org\/10.1016\/0020-0190(86)90058-X","journal-title":"Inf. Process. Lett."},{"key":"12_CR12","doi-asserted-by":"publisher","unstructured":"Holtmann, M., Kaiser, L., Thomas, W.: Degrees of lookahead in regular infinite games. Logical Methods in Computer Science 8(3) (2012). https:\/\/doi.org\/10.2168\/LMCS-8(3:24)2012","DOI":"10.2168\/LMCS-8(3:24)2012"},{"key":"12_CR13","doi-asserted-by":"publisher","unstructured":"II, K.C., Pachl, J.K.: Equivalence problems for mappings on infinite strings. Information and Control 49(1), 52\u201363 (1981). https:\/\/doi.org\/10.1016\/S0019-9958(81)90444-7","DOI":"10.1016\/S0019-9958(81)90444-7"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.2307\/1994916","volume":"138","author":"JR B\u00fcchi","year":"1969","unstructured":"B\u00fcchi, J.R., Landweber, L.H.: Solving sequential conditions finite-state strategies. Transactions of the American Mathematical Society 138, 295\u2013311 (1969). https:\/\/doi.org\/10.2307\/1994916","journal-title":"Transactions of the American Mathematical Society"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Kaminski, M., Francez, N.: Finite-memory automata. Theor. Comput. Sci. 134(2), 329\u2013363 (Nov 1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90242-9","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Khalimov, A., Kupferman, O.: Register-bounded synthesis. In: 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, Amsterdam, the Netherlands. pp. 25:1\u201325:16 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2019.25","DOI":"10.4230\/LIPIcs.CONCUR.2019.25"},{"key":"12_CR17","doi-asserted-by":"publisher","unstructured":"Khalimov, A., Maderbacher, B., Bloem, R.: Bounded synthesis of register transducers. In: Automated Technology for Verification and Analysis, 16th International Symposium, ATVA 2018, Los Angeles, October 7-10, 2018. Proceedings (2018). https:\/\/doi.org\/10.1007\/978-3-030-01090-4_29","DOI":"10.1007\/978-3-030-01090-4_29"},{"issue":"7","key":"12_CR18","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1016\/j.jcss.2015.03.005","volume":"81","author":"L Libkin","year":"2015","unstructured":"Libkin, L., Tan, T., Vrgoc, D.: Regular expressions for data words. J. Comput. Syst. Sci. 81(7), 1278\u20131297 (2015). https:\/\/doi.org\/10.1016\/j.jcss.2015.03.005","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"12_CR19","doi-asserted-by":"publisher","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. Logic 5(3), 403\u2013435 (2004). https:\/\/doi.org\/10.1145\/1013560.1013562","journal-title":"ACM Trans. Comput. Logic"},{"key":"12_CR20","doi-asserted-by":"publisher","unstructured":"Pnueli, A., Rosner, R.: On the synthesis of a reactive module. In: ACM Symposium on Principles of Programming Languages, POPL. ACM (1989). https:\/\/doi.org\/10.1145\/75277.75293","DOI":"10.1145\/75277.75293"},{"issue":"1-2","key":"12_CR21","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0304-3975(01)00307-3","volume":"276","author":"C Prieur","year":"2002","unstructured":"Prieur, C.: How to decide continuity of rational functions on infinite words. Theor. Comput. Sci. 276(1-2), 445\u2013447 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00307-3","journal-title":"Theor. Comput. Sci."}],"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-45231-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T13:31:57Z","timestamp":1610026317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-45231-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030452308","9783030452315"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45231-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 April 2020","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":"Dublin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/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":"98","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":"31","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","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":"12","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":"The conference could not take place due to the COVID-19 pandemic. There was an online event on July 2, 2020.","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)"}}]}}