×

Rational series with high image complexity. (English) Zbl 1371.68152

Summary: By using the universal Diophantine representation of recursively enumerable sets of positive integers due to Matiyasevich we construct a \(\mathbb 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^{-1}r\) where \(w \in X^\ast\). As a consequence we obtain various undecidability results for \(\mathbb Z\)-rational series.

MSC:

68Q45 Formal languages and automata
03B25 Decidability of theories and sets of sentences
03D05 Automata and formal grammars in connection with logical questions
03D25 Recursively (computably) enumerable sets and degrees
11U05 Decidability (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI