Rational series with high image complexity
EDP SCIENCES S A
Pysyvä osoite
Verkkojulkaisu
Tiivistelmä
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.