A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Degrees of infinite words, polynomials and atoms
Tekijät: Jörg Endrullis, Juhani Karhumäki, Jan Willem Klop, Aleksi Saarela
Toimittaja: Srečko Brlek, Christophe Reutenauer
Konferenssin vakiintunut nimi: International Conference on Developments in Language Theory
Julkaisuvuosi: 2016
Kokoomateoksen nimi: Developments in Language Theory: 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings
Sarjan nimi: Lecture Notes in Computer Science
Numero sarjassa: 9840
Vuosikerta: 9840
Aloitussivu: 164
Lopetussivu: 176
Sivujen määrä: 13
ISBN: 978-3-662-53131-0
eISBN: 978-3-662-53132-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-662-53132-7_14
Our objects of study are 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.
We use methods
from linear algebra and analysis to show that there is an infinite
number of atoms in the transducer degrees, that is, minimal non-trivial
degrees.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
