Iteration of rational transductions

 Access to full text

 Full (PDF)

1. [1] A. Avizienis, Signed-digit number representations for fast parallel arithmetic. IRE Trans. Electronic Computers 10 (1961) 389-400. MR135213
2. [2] J. Berstel, Transductions and Context-Free Languages. Teubner Studienbücher, Stuttgart (1979). Zbl0424.68040MR549481
3. [3] M. Clerbout and M. Latteux, Partial commutations and faithful rational transductions. Theoret. Comput. Sci. 34 (1984) 241-254. Zbl0548.68073MR773455
4. [4] S. Eilenberg, Automata, Languages and Machines, Vol. A. Academic Press, New York (1974). Zbl0317.94045MR530382
5. [5] C. C. Elgot and J. E. Mezei, On relations defined by generalized finite automata. IBM J. Res. Develop. 9 (1965) 47-68. Zbl0135.00704MR216903
6. [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. MR1470021
7. [7] S. A. Greibach, Pull AFL's and nested iterated substitution. Inform. and Control (Shenyang) 16 (1970) 7-35. Zbl0188.03102MR269446
8. [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. MR1469999
9. [9] N. Immerman, Nondeterministic space is closed under complementation. SIAM J. Comput. 17 (1988) 935-938. Zbl0668.68056MR961049
10. [10] S.-Y. Kuroda, Classes of languages and linear bounded automata. Inform. and Control (Shenyang) 7 (1964) 207-223. Zbl0199.04002MR169724
11. [11] M. Latteux and D. Simplot, Recognizable picture languages and domino tiling. Theoret. Comput. Sci. 178 (1997) 275-283. Zbl0912.68106MR1453855
12. [12] M Latteux and D. Simplot, Context-sensitive string languages and recognizable picture languages. Inform. and Comput. 138 (1997) 160-169. Zbl0895.68083MR1479320
13. [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. MR1684072
14. [14] M. Latteux and P. Turakainen, On characterizations of recursively enumerable languages. Acta Inform. 28 (1990) 179-186. Zbl0686.68060MR1089688
15. [15] J. Leguy, Transductions rationnelles décroissantes. RAIRO Theoret. Informatics Appl. 15 (1981) 141-148. Zbl0456.68097MR618451
16. [16] É. Lilin, Une généralisation des semi-commutations. Tech. Rep. it-210, L.I.F.L., Université Lille 1, France (1991). 
17. [17] J.-M. Muller, Some characterizations of functions computable in on-line arithmetic. IEEE Trans. Comput. 43 (1994) 752-755. Zbl1042.68503MR1284161
18. [18] M. Nivat, Transductions des langages de Chomsky. Ann. Inst. Fourier (Grenoble) 18 (1968) 339-456. Zbl0313.68065MR238633
19. [19] M.P. Schützenberger, Sur les relations rationnelles entre monoïdes libres. Theoret. Comput. Sci. 3 (1976) 243-259. Zbl0358.68129MR445927
20. [20] D. Simplot and A. TerlutteClosure under union and composition of iterated rational transductions (in preparation). Zbl0970.68085
21. [21] R. Szelepcsényi, The method of forced enumeration for nondeterministic automata. Acta Inform. 26 (1988) 279-284. Zbl0638.68046MR975334
22. [22] M. Szijártó, A classification and closure properties of languages for describing concurrent System behaviours. Fund. Inform. 4 (1981) 531-549. Zbl0486.68074MR678010
23. [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. Zbl0541.68045MR748525
24. [24] D. Wood, Iterated a-NGSM maps and T Systems. Inform. and Control (Shenyang) 32 (1976) 1-26. Zbl0346.68036MR416130