Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :