{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:08Z","timestamp":1753894388239,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Regular functions from infinite words to infinite words can be equivalently\nspecified by MSO-transducers, streaming $\\omega$-string transducers as well as\ndeterministic two-way transducers with look-ahead. In their one-way\nrestriction, the latter transducers define the class of rational functions.\nEven though regular functions are robustly characterised by several\nfinite-state devices, even the subclass of rational functions may contain\nfunctions which are not computable (by a Turing machine with infinite input).\nThis paper proposes a decision procedure for the following synthesis problem:\ngiven a regular function $f$ (equivalently specified by one of the\naforementioned transducer model), is $f$ computable and if it is, synthesize a\nTuring machine computing it.\n  For regular functions, we show that computability is equivalent to\ncontinuity, and therefore the problem boils down to deciding continuity. We\nestablish a generic characterisation of continuity for functions preserving\nregular languages under inverse image (such as regular functions). We exploit\nthis characterisation to show the decidability of continuity (and hence\ncomputability) of rational and regular functions. For rational functions, we\nshow that this can be done in $\\mathsf{NLogSpace}$ (it was already known to be\nin $\\mathsf{PTime}$ by Prieur). In a similar fashion, we also effectively\ncharacterise uniform continuity of regular functions, and relate it to the\nnotion of uniform computability, which offers stronger efficiency guarantees.<\/jats:p>","DOI":"10.46298\/lmcs-18(2:23)2022","type":"journal-article","created":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T19:27:54Z","timestamp":1656617274000},"source":"Crossref","is-referenced-by-count":0,"title":["Synthesis of Computable Regular Functions of Infinite Words"],"prefix":"10.46298","volume":"Volume 18, Issue 2","author":[{"given":"V.","family":"Dave","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Filiot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Krishna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N.","family":"Lhote","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,6,29]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9750\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9750\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:20:09Z","timestamp":1687292409000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/7592"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,29]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(2:23)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"1906.04199v3","asserted-by":"subject"},{"id-type":"arxiv","id":"1906.04199v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1906.04199","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1906.04199","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,6,29]]},"article-number":"7592"}}