Rational series with high image complexity
Honkala, Juha1
1 Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 1, pp. 1-6.

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 -1 r where w∈X * . As a consequence we obtain various undecidability results for Z-rational series.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2017001
Classification : 68Q45, 03B25, 11U05
Mots-clés : Rational series, recursively enumerable set, Diophantine representation, undecidability
Honkala, Juha 1

1 Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland. 
@article{ITA_2017__51_1_1_0,
     author = {Honkala, Juha},
     title = {Rational series with high image complexity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {1--6},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {1},
     year = {2017},
     doi = {10.1051/ita/2017001},
     mrnumber = {3678025},
     zbl = {1371.68152},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2017001/}
}
TY  - JOUR
AU  - Honkala, Juha
TI  - Rational series with high image complexity
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2017
SP  - 1
EP  - 6
VL  - 51
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2017001/
DO  - 10.1051/ita/2017001
LA  - en
ID  - ITA_2017__51_1_1_0
ER  - 
%0 Journal Article
%A Honkala, Juha
%T Rational series with high image complexity
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2017
%P 1-6
%V 51
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2017001/
%R 10.1051/ita/2017001
%G en
%F ITA_2017__51_1_1_0
Honkala, Juha. Rational series with high image complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 1, pp. 1-6. doi : 10.1051/ita/2017001. http://archive.numdam.org/articles/10.1051/ita/2017001/

J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer, Berlin (1988). | MR | Zbl

J. Berstel and C. Reutenauer, Noncommutative Rational Series With Applications. Cambridge University Press, Cambridge (2011). | MR | Zbl

E. Charlier and J. Honkala, The freeness problem over matrix semigroups and bounded languages. Inf. Comput. 237 (2014) 243–256. | DOI | MR | Zbl

J. Honkala, Products of matrices and recursively enumerable sets. J. Comput. Syst. Sci. 81 (2015) 468–472. | DOI | MR | Zbl

W. Kuich and A. Salomaa, Semirings, Automata, Languages. Springer, Berlin (1986). | MR | Zbl

Y. Matiyasevich, Hilbert’s Tenth Problem, MIT Press, Cambridge (1993). | MR | Zbl

A. Salomaa, Computation and Automata. Springer, Berlin (1985). | Zbl

A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer, Berlin (1978). | MR | Zbl

Cité par Sources :