Rational series with high image complexity

: Juha Honkala

Publisher: EDP SCIENCES S A

: 2017

: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications

: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS

: RAIRO-THEOR INF APPL

: 51

: 1

: 6

: 0988-3754

: 1290-385X

DOI: https://doi.org/10.1051/ita/2017001

: 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.

ita160045.pdf