{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:11Z","timestamp":1753894391458,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T00:00:00Z","timestamp":1659052800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-18-CE40-0015"],"award-info":[{"award-number":["ANR-18-CE40-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","award":["ANR-16-CE40-0007"],"award-info":[{"award-number":["ANR-16-CE40-0007"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>In this paper, we investigate the problem of synthesizing computable\nfunctions of infinite words over an infinite alphabet (data $\\omega$-words).\nThe notion of computability is defined through Turing machines with infinite\ninputs which can produce the corresponding infinite outputs in the limit. We\nuse non-deterministic transducers equipped with registers, an extension of\nregister automata with outputs, to describe specifications. Being\nnon-deterministic, such transducers may not define functions but more generally\nrelations of data $\\omega$-words. In order to increase the expressive power of\nthese machines, we even allow guessing of arbitrary data values when updating\ntheir registers.\n  For functions over data $\\omega$-words, we identify a sufficient condition\n(the possibility of determining the next letter to be outputted, which we call\nnext letter problem) under which computability (resp. uniform computability)\nand continuity (resp. uniform continuity) coincide.\n  We focus on two kinds of data domains: first, the general setting of\noligomorphic data, which encompasses any data domain with equality, as well as\nthe setting of rational numbers with linear order; and second, the set of\nnatural numbers equipped with linear order. For both settings, we prove that\nfunctionality, i.e. determining whether the relation recognized by the\ntransducer is actually a function, is decidable. We also show that the\nso-called next letter problem is decidable, yielding equivalence between\n(uniform) continuity and (uniform) computability. Last, we provide\ncharacterizations of (uniform) continuity, which allow us to prove that these\nnotions, and thus also (uniform) computability, are decidable. We even show\nthat all these decision problems are PSpace-complete for $(\\mathbb{N},&lt;)$ and\nfor a large class of oligomorphic data domains, including for instance\n$(\\mathbb{Q},&lt;)$.<\/jats:p>","DOI":"10.46298\/lmcs-18(3:9)2022","type":"journal-article","created":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T13:10:09Z","timestamp":1659100209000},"source":"Crossref","is-referenced-by-count":0,"title":["Computability of Data-Word Transductions over Different Data Domains"],"prefix":"10.46298","volume":"Volume 18, Issue 3","author":[{"given":"L\u00e9o","family":"Exibard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanuel","family":"Filiot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Lhote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre-Alain","family":"Reynier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,7,29]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9861\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9861\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:19:29Z","timestamp":1687292369000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,29]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(3:9)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"2101.07038v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2101.07038v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2101.07038v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2101.07038","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2101.07038","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,7,29]]},"article-number":"7104"}}