The cyclicity problem for the images of Q-rational series
Honkala, Juha
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011), p. 375-381 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2011-01-01
DOI : https://doi.org/10.1051/ita/2011111
Classification:  11B85,  11U05,  68Q45 
@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},
     volume = {45},
     year = {2011},
     pages = {375-381},
     doi = {10.1051/ita/2011111},
     mrnumber = {2876112},
     zbl = {1261.11027},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 375-381. doi : 10.1051/ita/2011111. http://gdmltest.u-ga.fr/item/ITA_2011__45_4_375_0/

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

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

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

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

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

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