Iteration of rational transductions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 2, pp. 99-129.
@article{ITA_2000__34_2_99_0,
     author = {Terlutte, Alain and Simplot, David},
     title = {Iteration of rational transductions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {99--129},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {2},
     year = {2000},
     mrnumber = {1774304},
     zbl = {0962.68090},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2000__34_2_99_0/}
}
TY  - JOUR
AU  - Terlutte, Alain
AU  - Simplot, David
TI  - Iteration of rational transductions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 99
EP  - 129
VL  - 34
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2000__34_2_99_0/
LA  - en
ID  - ITA_2000__34_2_99_0
ER  - 
%0 Journal Article
%A Terlutte, Alain
%A Simplot, David
%T Iteration of rational transductions
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 99-129
%V 34
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2000__34_2_99_0/
%G en
%F ITA_2000__34_2_99_0
Terlutte, Alain; Simplot, David. Iteration of rational transductions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 2, pp. 99-129. http://archive.numdam.org/item/ITA_2000__34_2_99_0/

[1] A. Avizienis, Signed-digit number representations for fast parallel arithmetic. IRE Trans. Electronic Computers 10 (1961) 389-400. | MR

[2] J. Berstel, Transductions and Context-Free Languages. Teubner Studienbücher, Stuttgart (1979). | MR | Zbl

[3] M. Clerbout and M. Latteux, Partial commutations and faithful rational transductions. Theoret. Comput. Sci. 34 (1984) 241-254. | MR | Zbl

[4] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974). | MR | Zbl

[5] C. C. Elgot and J. E. Mezei, On relations defined by generalized finite automata. IBM J. Res. Develop. 9 (1965) 47-68. | MR | Zbl

[6] D. Giammarresi and A. Restivo, Two-dimensional languages, in Handbook of Formal Languages, edited by A. Salomaa and G. Rozenberg, Vol. 3. Springer-Verlag, Berlin (1997) 215-267. | MR

[7] S. A. Greibach, Pull AFL's and nested iterated substitution. Inform. and Control (Shenyang) 16 (1970) 7-35. | MR | Zbl

[8] T. Harju and J. Karhumäki, Morphism, in Handbook of Formal Languages, edited by A. Salomaa and G. Rozenberg, Vol. 1. Springer-Verlag, Berlin (1997) 439-510. | MR

[9] N. Immerman, Nondeterministic space is closed under complementation. SIAM J. Comput. 17 (1988) 935-938. | MR | Zbl

[10] S.-Y. Kuroda, Classes of languages and linear bounded automata. Inform. and Control (Shenyang) 7 (1964) 207-223. | MR | Zbl

[11] M. Latteux and D. Simplot, Recognizable picture languages and domino tiling. Theoret. Comput. Sci. 178 (1997) 275-283. | MR | Zbl

[12] M Latteux and D. Simplot, Context-sensitive string languages and recognizable picture languages. Inform. and Comput. 138 (1997) 160-169. | MR | Zbl

[13] M. Latteux, D. Simplot and A. Terlutte, Iterated length-preserving rational transduction, 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. | MR

[14] M. Latteux and P. Turakainen, On characterizations of recursively enumerable languages. Acta Inform. 28 (1990) 179-186. | MR | Zbl

[15] J. Leguy, Transductions rationnelles décroissantes. RAIRO Theoret. Informatics Appl. 15 (1981) 141-148. | Numdam | MR | Zbl

[16] É. Lilin, Une généralisation des semi-commutations. Tech. Rep. it-210, L.I.F.L., Université Lille 1, France (1991).

[17] J.-M. Muller, Some characterizations of functions computable in on-line arithmetic. IEEE Trans. Comput. 43 (1994) 752-755. | MR | Zbl

[18] M. Nivat, Transductions des langages de Chomsky. Ann. Inst. Fourier (Grenoble) 18 (1968) 339-456. | Numdam | MR | Zbl

[19] M.P. Schützenberger, Sur les relations rationnelles entre monoïdes libres. Theoret. Comput. Sci. 3 (1976) 243-259. | MR | Zbl

[20] D. Simplot and A. Terlutte Closure under union and composition of iterated rational transductions (in preparation). | Numdam | Zbl

[21] R. Szelepcsényi, The method of forced enumeration for nondeterministic automata. Acta Inform. 26 (1988) 279-284. | MR | Zbl

[22] M. Szijártó, A classification and closure properties of languages for describing concurrent System behaviours. Fund. Inform. 4 (1981) 531-549. | MR | Zbl

[23] P. Turakainen, Transducers and compositions of morphisms and inverse morphisms, in Studies in honour of Arto Kustaa Salomaa on the occasion of his fiftieth birthday. Ann. Univ. Turku. Ser. A I 186 (1984) 118-128. | MR | Zbl

[24] D. Wood, Iterated a-NGSM maps and T Systems. Inform. and Control (Shenyang) 32 (1976) 1-26. | MR | Zbl