{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T15:01:58Z","timestamp":1648911718393},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","funder":[{"name":"the DeLTA","award":["ANR-16-CE40-0007"],"award-info":[{"award-number":["ANR-16-CE40-0007"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p> Transducers constitute a fundamental extension of automata. The class of regular word functions has recently emerged as an important class of word-to-word functions, characterized by means of (functional, or unambiguous, or deterministic) two-way transducers, copyless streaming string transducers, and MSO-definable graph transformations. A fundamental result in language theory is Kleene\u2019s Theorem, relating finite state automata and regular expressions. Recently, a set of regular function expressions has been introduced and used to prove a similar result for regular word functions, by showing its equivalence with copyless streaming string transducers. In this paper, we propose a direct, simplified and effective translation from unambiguous two-way transducers to regular function expressions extending the Brzozowski and McCluskey algorithm. In addition, our approach allows us to derive a subset of regular function expressions characterizing the (strict) subclass of functional sweeping transducers. <\/jats:p>","DOI":"10.1142\/s0129054120410087","type":"journal-article","created":{"date-parts":[[2020,10,5]],"date-time":"2020-10-05T08:11:59Z","timestamp":1601885519000},"page":"843-873","source":"Crossref","is-referenced-by-count":0,"title":["From Two-Way Transducers to Regular Function Expressions"],"prefix":"10.1142","volume":"31","author":[{"given":"Nicolas","family":"Baudru","sequence":"first","affiliation":[{"name":"Aix Marseille Univ, Universit\u00e9 de Toulon, CNRS, LIS, Marseille, France"}]},{"given":"Pierre-Alain","family":"Reynier","sequence":"additional","affiliation":[{"name":"Aix Marseille Univ, Universit\u00e9 de Toulon, CNRS, LIS, Marseille, France"}]}],"member":"219","published-online":{"date-parts":[[2020,10,5]]},"reference":[{"key":"S0129054120410087BIB002","first-page":"65","volume-title":"LICS","author":"Alur R.","year":"2012"},{"key":"S0129054120410087BIB003","first-page":"9:1","volume-title":"CSL-LICS\u201914","author":"Alur R.","year":"2014"},{"key":"S0129054120410087BIB004","first-page":"1","volume-title":"LICS\u201917","author":"Baschenis F.","year":"2017"},{"key":"S0129054120410087BIB005","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/978-3-319-98654-8_8","volume-title":"Developments in Language Theory \u2014 22nd International Conference, DLT 2018","volume":"11088","author":"Baudru N.","year":"2018"},{"key":"S0129054120410087BIB006","volume-title":"Teubner Studienb\u00fccher: Informatik","volume":"38","author":"Berstel J.","year":"1979"},{"key":"S0129054120410087BIB007","series-title":"LNCS","first-page":"26","volume-title":"ICALP 2014","volume":"8573","author":"Bojanczyk M.","year":"2014"},{"issue":"2","key":"S0129054120410087BIB008","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/PGEC.1963.263416","volume":"12","author":"Brzozowski J. A.","year":"1963","journal-title":"IEEE Trans. Electronic Computers"},{"key":"S0129054120410087BIB010","series-title":"LNCS","first-page":"196","volume-title":"MFCS","volume":"8634","author":"Choffrut C.","year":"2014"},{"issue":"1","key":"S0129054120410087BIB011","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"Courcelle B.","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120410087BIB012","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/3209108.3209182","volume-title":"LICS","author":"Dave V.","year":"2018"},{"issue":"2","key":"S0129054120410087BIB013","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1145\/371316.371512","volume":"2","author":"Engelfriet J.","year":"2001","journal-title":"ACM Trans. Comput. Log."},{"key":"S0129054120410087BIB014","first-page":"468","volume-title":"LICS","author":"Filiot E.","year":"2013"},{"key":"S0129054120410087BIB016","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft J. E.","year":"1979"},{"issue":"4","key":"S0129054120410087BIB017","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1051\/ita\/2016026","volume":"50","author":"Lombardy S.","year":"2016","journal-title":"RAIRO \u2014 Theor. Inf. and Applic."},{"key":"S0129054120410087BIB018","volume-title":"Counter-Free Automata","author":"McNaughton R.","year":"1971"},{"issue":"1","key":"S0129054120410087BIB019","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/TEC.1960.5221603","volume":"9","author":"McNaughton R.","year":"1960","journal-title":"IRE Trans. Electron. Comput."},{"issue":"2","key":"S0129054120410087BIB020","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"Sch\u00fctzenberger M. P.","year":"1961","journal-title":"Information and Control"},{"issue":"1","key":"S0129054120410087BIB021","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0304-3975(90)90047-L","volume":"72","author":"Simon I.","year":"1990","journal-title":"Theor. Comput. Sci."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120410087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T08:58:55Z","timestamp":1605257935000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120410087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":18,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1142\/S0129054120410087"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120410087","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}