The cyclicity problem for the images of Q-rational series
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 375-381.

We show that it is decidable whether or not a given Q-rational series in several noncommutative variables has a cyclic image. By definition, a series r has a cyclic image if there is a rational number q such that all nonzero coefficients of r are integer powers of q.

DOI : 10.1051/ita/2011111
Classification : 11B85, 11U05, 68Q45
Mots-clés : rational series, images of rational series, decidability 
@article{ITA_2011__45_4_375_0,
     author = {Honkala, Juha},
     title = {The cyclicity problem for the images of {Q-rational} series},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {375--381},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {4},
     year = {2011},
     doi = {10.1051/ita/2011111},
     mrnumber = {2876112},
     zbl = {1261.11027},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2011111/}
}
TY  - JOUR
AU  - Honkala, Juha
TI  - The cyclicity problem for the images of Q-rational series
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 375
EP  - 381
VL  - 45
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2011111/
DO  - 10.1051/ita/2011111
LA  - en
ID  - ITA_2011__45_4_375_0
ER  - 
%0 Journal Article
%A Honkala, Juha
%T The cyclicity problem for the images of Q-rational series
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 375-381
%V 45
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2011111/
%R 10.1051/ita/2011111
%G en
%F ITA_2011__45_4_375_0
Honkala, Juha. The cyclicity problem for the images of Q-rational series. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 375-381. doi : 10.1051/ita/2011111. http://archive.numdam.org/articles/10.1051/ita/2011111/

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

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

[3] G. Jacob, La finitude des représentations linéaires des semi-groupes est décidable. J. Algebra 52 (1978) 437-459. | MR | Zbl

[4] G. Polya, Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen. J. Reine Angew. Math. 151 (1921) 1-31. | JFM

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

[6] M.-P. Schützenberger, On the definition of a family of automata, Inf. Control 4 (1961) 245-270. | MR | Zbl

Cité par Sources :