The cyclicity problem for the images of Q-rational series
RAIRO - Theoretical Informatics and Applications (2012)
- Volume: 45, Issue: 4, page 375-381
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topHonkala, Juha. "The cyclicity problem for the images of Q-rational series." RAIRO - Theoretical Informatics and Applications 45.4 (2012): 375-381. <http://eudml.org/doc/221994>.
@article{Honkala2012,
abstract = {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. },
author = {Honkala, Juha},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Rational series; images of rational series; decidability; -rational series; set of coefficients of -rational series; non-commutative variables},
language = {eng},
month = {1},
number = {4},
pages = {375-381},
publisher = {EDP Sciences},
title = {The cyclicity problem for the images of Q-rational series},
url = {http://eudml.org/doc/221994},
volume = {45},
year = {2012},
}
TY - JOUR
AU - Honkala, Juha
TI - The cyclicity problem for the images of Q-rational series
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/1//
PB - EDP Sciences
VL - 45
IS - 4
SP - 375
EP - 381
AB - 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.
LA - eng
KW - Rational series; images of rational series; decidability; -rational series; set of coefficients of -rational series; non-commutative variables
UR - http://eudml.org/doc/221994
ER -
References
top- J. Berstel and C. Reutenauer, Rational Series and Their Languages. Springer, Berlin (1988).
- J. Berstel and C. Reutenauer, Noncommutative Rational Series with Applications. Cambridge University Press, Cambridge (2011).
- G. Jacob, La finitude des représentations linéaires des semi-groupes est décidable. J. Algebra52 (1978) 437–459.
- G. Polya, Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen. J. Reine Angew. Math.151 (1921) 1–31.
- A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Springer, Berlin (1978).
- M.-P. Schützenberger, On the definition of a family of automata, Inf. Control4 (1961) 245–270.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.