Closure under union and composition of iterated rational transductions

D. Simplot; A. Terlutte

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 3, page 183-212
  • ISSN: 0988-3754

Abstract

top
We proceed our work on iterated transductions by studying the closure under union and composition of some classes of iterated functions. We analyze this closure for the classes of length-preserving rational functions, length-preserving subsequential functions and length-preserving sequential functions with terminal states. All the classes we obtain are equal. We also study the connection with deterministic context-sensitive languages.

How to cite

top

Simplot, D., and Terlutte, A.. "Closure under union and composition of iterated rational transductions." RAIRO - Theoretical Informatics and Applications 34.3 (2010): 183-212. <http://eudml.org/doc/221990>.

@article{Simplot2010,
abstract = { We proceed our work on iterated transductions by studying the closure under union and composition of some classes of iterated functions. We analyze this closure for the classes of length-preserving rational functions, length-preserving subsequential functions and length-preserving sequential functions with terminal states. All the classes we obtain are equal. We also study the connection with deterministic context-sensitive languages. },
author = {Simplot, D., Terlutte, A.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Rational transductions; rational functions; iteration of transductions; context-sensitive languages.; context-sensitive languages},
language = {eng},
month = {3},
number = {3},
pages = {183-212},
publisher = {EDP Sciences},
title = {Closure under union and composition of iterated rational transductions},
url = {http://eudml.org/doc/221990},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Simplot, D.
AU - Terlutte, A.
TI - Closure under union and composition of iterated rational transductions
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 3
SP - 183
EP - 212
AB - We proceed our work on iterated transductions by studying the closure under union and composition of some classes of iterated functions. We analyze this closure for the classes of length-preserving rational functions, length-preserving subsequential functions and length-preserving sequential functions with terminal states. All the classes we obtain are equal. We also study the connection with deterministic context-sensitive languages.
LA - eng
KW - Rational transductions; rational functions; iteration of transductions; context-sensitive languages.; context-sensitive languages
UR - http://eudml.org/doc/221990
ER -

References

top
  1. A. Arnold and M. Latteux, A new proof of two theorems about rational transductions. Theoret. Comput. Sci.8 (1979) 261-263.  
  2. J. Berstel, Transductions and Context-Free Languages. Teubner Studienbücher, Stuttgart (1979).  
  3. S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974).  
  4. C.C. Elgot and J.E. Mezei, On relations defined by generalized finite automata. IBM J. Res. Develop.9 (1965) 47-68.  
  5. M. Latteux, D. Simplot and A. Terlutte, Iterated length-preserving rational transductions, in Proc. 23rd Symposium on Mathematical Foundations of Computer Science (MFCS'98) (Brno, Czech Republic, 1998), edited by L. Brim, J. Gruska and J. Zlatuska. Springer-Verlag, Berlin, Lecture Notes in Comput. Sci.1450 (1998) 286-295.  
  6. J. Leguy, Transductions rationnelles décroissantes. Theoret. Informatics Appl.15 (1981) 141-148.  
  7. M. Nivat, Transductions des langages de Chomsky. Ann. Inst. Fourier (Grenoble)18 (1968) 339-456.  
  8. M.P. Schützenberger, Sur les relations rationnelles entre monoïdes libres. Theoret. Comput. Sci.3 (1976) 243-259.  
  9. D. Simplot and A. Terlutte, Iterations of Transductions. Theoret. Informatics Appl.34 (2000) 99-130.  
  10. D. Wood, Iterated a-NGSM maps and Γ systems. Inform. and Control32 (1976) 1-26.  

NotesEmbed ?

top

You must be logged in to post comments.