A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Degrees of Infinite Words, Polynomials and Atoms




TekijätEndrullis J, Karhumaki J, Klop JW, Saarela A

KustantajaWORLD SCIENTIFIC PUBL CO PTE LTD

Julkaisuvuosi2018

JournalInternational Journal of Foundations of Computer Science

Tietokannassa oleva lehden nimiINTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Lehden akronyymiINT J FOUND COMPUT S

Vuosikerta29

Numero05

Aloitussivu825

Lopetussivu843

Sivujen määrä19

ISSN0129-0541

eISSN1793-6373

DOIhttps://doi.org/10.1142/S0129054118420066

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/35741209


Tiivistelmä
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.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.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.

Ladattava julkaisu

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 13:26