A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Rational series with high image complexity
Tekijät: Juha Honkala
Kustantaja: EDP SCIENCES S A
Julkaisuvuosi: 2017
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Lehden akronyymi: RAIRO-THEOR INF APPL
Vuosikerta: 51
Numero: 1
Aloitussivu: 1
Lopetussivu: 6
Sivujen määrä: 6
ISSN: 0988-3754
eISSN: 1290-385X
DOI: https://doi.org/10.1051/ita/2017001
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/26958894
By using the universal Diophantine representation of recursively enumerable sets of positive integers due to Matiyasevich we construct a Z-rational series gamma Over a binary alphabet X which has a maximal image complexity in the sense that all recursively enumerable sets of positive integers are obtained as the sets of positive coefficients of the series w(-1)gamma where w. X-*. As a consequence we obtain various undecidability results for Z-rational series.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
