Iteration of rational transductions
Terlutte, Alain ; Simplot, David
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 99-129 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@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},
     volume = {34},
     year = {2000},
     pages = {99-129},
     mrnumber = {1774304},
     zbl = {0962.68090},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 99-129. http://gdmltest.u-ga.fr/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 135213

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

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

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

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

[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 1470021

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

[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 1469999

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

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

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

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

[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 1684072

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

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

[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 1284161 | Zbl 1042.68503

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

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

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

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

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

[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 748525 | Zbl 0541.68045

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