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

Abstract

top
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.

How to cite

top

Angrand, 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
  1. P.-Y. Angrand, J. Sakarovitch and R. de Souza, Sequential transducer cascades. In preparation.  
  2. J. Berstel, Transductions and Context-Free Languages. Teubner (1979).  
  3. 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.  
  4. V. Berthé, Ch. Frougny, M. Rigo and J. Sakarovitch, On the concrete complexity of the successor function. In preparation.  
  5. 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.  
  6. 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.  
  7. S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press (1974).  
  8. P. Lecomte and M. Rigo, Numeration systems on a regular language. Theor. Comput. Syst.34 (2001) 27–44.  
  9. D. Perrin, Finite automata. Handbook of Theoretical Computer Science Vol. B, edited by J. van Leeuwen. Elsevier (1990) 1–53.  
  10. 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.  
  11. J. Sakarovitch, Deux remarques sur un théorème de S. Eilenberg. RAIRO-Theor. Inf. Appl.17 (1983) 23–48.  
  12. J. Sakarovitch, Eléments de théorie des automates. Vuibert (2003). English corrected edition: Elements of Automata Theory, Cambridge University Press (2009).  
  13. M.P. Schützenberger, Sur une variante des fonctions séquentielles. Theoret. Comput. Sci.4 (1977) 47–57.  
  14. J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113 (1994) 331–347.  

NotesEmbed ?

top

You must be logged in to post comments.