A1 Refereed original research article in a scientific journal
Rational series with high image complexity
Authors: Juha Honkala
Publisher: EDP SCIENCES S A
Publication year: 2017
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Journal acronym: RAIRO-THEOR INF APPL
Volume: 51
Issue: 1
First page : 1
Last page: 6
Number of pages: 6
ISSN: 0988-3754
eISSN: 1290-385X
DOI: https://doi.org/10.1051/ita/2017001(external)
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/26958894(external)
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.
Downloadable publication This is an electronic reprint of the original article. |  |
