On the Problem Whether the Image of an N-Rational Series Equals

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Honkala, Juha

Affiliations: Department of Mathematics University of Turku FIN-20014 Turku, Finland. E-mail: [email protected]

Abstract: We show that it is undecidable whether or not a given N-rational series assumes all nonnegative values. As a consequence we see that it is undecidable whether the image of a given N-rational series equals the image of a given N-rational sequence. We discuss also related results concerning DT0L and D0L length sets.

Keywords: N-rational series, decidability

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 127-132, 2006