{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T09:26:35Z","timestamp":1770801995709,"version":"3.50.0"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p> We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words. <\/jats:p><jats:p> The word transformation realised by finite-state transducers gives rise to a complexity comparison of words and thereby induces equivalence classes, called (transducer) degrees, and a partial order on these degrees. The ensuing hierarchy of degrees is analogous to the recursion-theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable words. Finite-state transducers give rise to a much more fine-grained, discriminating hierarchy. In contrast to Turing degrees, hardly anything is known about transducer degrees, in spite of their naturality. <\/jats:p><jats:p> We use methods from linear algebra and analysis to show that there are infinitely many atoms in the transducer degrees, that is, minimal non-trivial degrees. <\/jats:p>","DOI":"10.1142\/s0129054118420066","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T10:47:08Z","timestamp":1534848428000},"page":"825-843","source":"Crossref","is-referenced-by-count":3,"title":["Degrees of Infinite Words, Polynomials and Atoms"],"prefix":"10.1142","volume":"29","author":[{"given":"J\u00f6rg","family":"Endrullis","sequence":"first","affiliation":[{"name":"Department of Computer Science, Vrije Universiteit Amsterdam, Amsterdam, the Netherlands"}]},{"given":"Juhani","family":"Karhum\u00e4ki","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics &amp; FUNDIM, University of Turku, Turku, Finland"}]},{"given":"Jan Willem","family":"Klop","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Vrije Universiteit Amsterdam, Amsterdam, the Netherlands"},{"name":"Centrum Wiskunde &amp; Informatica (CWI), Amsterdam, the Netherlands"}]},{"given":"Aleksi","family":"Saarela","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics &amp; FUNDIM, University of Turku, Turku, Finland"}]}],"member":"219","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"S0129054118420066BIB001","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546563"},{"issue":"3","key":"S0129054118420066BIB002","first-page":"451","volume":"42","author":"Belov A.","year":"2008","journal-title":"ITA"},{"key":"S0129054118420066BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.034"},{"key":"S0129054118420066BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.indag.2016.11.004"},{"key":"S0129054118420066BIB009","author":"Endrullis J.","year":"2018","journal-title":"CoRR"},{"key":"S0129054118420066BIB012","volume-title":"Invitation to Mathematics","author":"Jacobs K.","year":"1992"},{"key":"S0129054118420066BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-2776-5_1"},{"key":"S0129054118420066BIB014","series-title":"Studies in logic and the foundations of mathematics","volume-title":"Classical Recursion Theory","author":"Odifreddi P.","year":"1999"},{"key":"S0129054118420066BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(74)80053-7"},{"key":"S0129054118420066BIB016","volume-title":"Elements of Automata Theory","author":"Sakarovitch J.","year":"2003"},{"key":"S0129054118420066BIB017","volume-title":"Jewels of Formal Language Theory","author":"Salomaa A.","year":"1981"},{"key":"S0129054118420066BIB018","volume-title":"Degrees of Unsolvability","author":"Shoenfield J. R.","year":"1971"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118420066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:58:18Z","timestamp":1565182698000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118420066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":12,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,8,21]]},"published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.1142\/S0129054118420066"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118420066","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}