Rational series with high image complexity

Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland.
juha.honkala@utu.fi

Received: 6 June 2016
Accepted: 2 January 2017

Abstract

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.