Rational series with high image complexity
Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland.
Received: 6 June 2016
Accepted: 2 January 2017
By using the universal Diophantine representation of recursively enumerable sets of positive integers due to Matiyasevich we construct a Z-rational series r 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-1r where w ∈ X∗. As a consequence we obtain various undecidability results for Z-rational series.
Mathematics Subject Classification: 68Q45 / 03B25 / 11U05
Key words: Rational series / recursively enumerable set / Diophantine representation / undecidability
© EDP Sciences 2017