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.  Zbl0376.94022
  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.  Zbl0605.68071
  7. S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press (1974).  Zbl0317.94045
  8. P. Lecomte and M. Rigo, Numeration systems on a regular language. Theor. Comput. Syst.34 (2001) 27–44.  Zbl0969.68095
  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.  Zbl0357.94024
  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.  Zbl0366.68043
  14. J. Shallit, Numeration systems, linear recurrences, and regular sets. Inform. Comput. 113 (1994) 331–347.  Zbl0810.11006

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.