Radix enumeration of rational languages
Pierre-Yves Angrand; Jacques Sakarovitch
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 44, Issue: 1, page 19-36
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topAngrand, Pierre-Yves, and Sakarovitch, Jacques. "Radix enumeration of rational languages." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 19-36. <http://eudml.org/doc/250779>.
@article{Angrand2010,
abstract = {
We prove that the function that maps a word of a rational language onto
its successor for the radix order in this language
is a finite union of co-sequential functions.
},
author = {Angrand, Pierre-Yves, Sakarovitch, Jacques},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Finite automata; rational functions of words; sequential transducers.; finite automata; sequential transducers},
language = {eng},
month = {2},
number = {1},
pages = {19-36},
publisher = {EDP Sciences},
title = {Radix enumeration of rational languages},
url = {http://eudml.org/doc/250779},
volume = {44},
year = {2010},
}
TY - JOUR
AU - Angrand, Pierre-Yves
AU - Sakarovitch, Jacques
TI - Radix enumeration of rational languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 19
EP - 36
AB -
We prove that the function that maps a word of a rational language onto
its successor for the radix order in this language
is a finite union of co-sequential functions.
LA - eng
KW - Finite automata; rational functions of words; sequential transducers.; finite automata; sequential transducers
UR - http://eudml.org/doc/250779
ER -
References
top- P.-Y. Angrand, J. Sakarovitch and R. de Souza, Sequential transducer cascades. In preparation.
- J. Berstel, Transductions and Context-Free Languages. Teubner (1979).
- V. Berthé, Ch. Frougny, M. Rigo and J. Sakarovitch, On the cost and complexity of the successor function, in Proc. WORDS 2007, edited by P. Arnoux, N. Bédaride and J. Cassaigne, Tech. Rep., Institut de mathématiques de Luminy (Marseille) (2007) 43–56.
- V. Berthé, Ch. Frougny, M. Rigo and J. Sakarovitch, On the concrete complexity of the successor function. In preparation.
- Ch. Choffrut, Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles. Theoret. Comput. Sci.5 (1977) 325–337.
- Ch. Choffrut and M.P. Schützenberger, Décomposition de fonctions rationnelles, Proc. STACS'86 , edited by B. Monien, G. Vidal-Naquet. Lect. Notes Comput. Sci.210 (1986) 213–226.
- S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press (1974).
- P. Lecomte and M. Rigo, Numeration systems on a regular language. Theor. Comput. Syst.34 (2001) 27–44.
- D. Perrin, Finite automata. Handbook of Theoretical Computer Science Vol. B, edited by J. van Leeuwen. Elsevier (1990) 1–53.
- Ch. Reutenauer, Une caractérisation de la finitude de l'ensemble des coefficients d'une série rationnelle en plusieurs variables non commutatives. C. R. Acad. Sci. Paris284 (1977) 1159–1162.
- J. Sakarovitch, Deux remarques sur un théorème de S. Eilenberg. RAIRO-Theor. Inf. Appl.17 (1983) 23–48.
- J. Sakarovitch, Eléments de théorie des automates. Vuibert (2003). English corrected edition: Elements of Automata Theory, Cambridge University Press (2009).
- M.P. Schützenberger, Sur une variante des fonctions séquentielles. Theoret. Comput. Sci.4 (1977) 47–57.
- J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113 (1994) 331–347.
Citations in EuDML Documents
topNotesEmbed ?
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.