Abstract
The purpose of this paper is the study of the smallest family of transductions containing length-preserving rational transductions and closed under union, composition and iteration. We give several characterizations of this class using restricted classes of length-preserving transductions, by showing the connections with “context-sensitive transductions” and transductions associated with recognizable picture languages. We also study the class obtained by only using length-preserving rational functions and we show the relations with “deterministic context-sensitive transductions”.
This work was partially supported by the group MOSYDIS of the PRC/GDR AMI
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Arnold, A., and Latteux, M.: A new proof of two theorems about rational transductions. Theoretical Computer Science 8, 2 (1979), 261–263.
Berstel, J.: Transductions and Context-Free Languages. Teubner Studienbücher, Stuttgart, 1979.
Eilenberg, S.: Automata, Languages and Machines, vol. A. Academic Press, New York, 1974.
Elgot, C. C., and Mezei, J. E.: On relations defined by generalized finite automata. IBM Journal of Research and Development 9 (1965), 47–68.
Giammarresi, D., and Restivo, A.: Two-dimensional languages. In Handbook of Formal Languages, A. Salomaa and G. Rozenberg, Eds., vol. 3. Springer-Verlag, Berlin, 1997, pp. 215–267.
Greibach, S. A.: Full AFL's and nested iterated substitution. Information and Control 16, 1 (1970), 7–35.
Kuroda, S.-Y.: Classes of languages and linear bounded automata. Information and Control 7, 2 (1964), 207–223.
Latteux, M., and Simplot, D.: Context-sensitive string languages and recognizable picture languages. Information and Computation 138, 2 (1997), 160–169.
Latteux, M., Simplot, D., and Terlutte, A.: Iterated length-preserving transductions. Tech. Rep. it-312, L.I.F.L., Univ. Lille 1 France, March 1998.
Mezei, J., and Wright, J. B.: Algebraic Automata and Context-Free Sets. Information and Control 11, 2–3 (1967), 3–29.
Nivat, M.: Transductions des langages de Chomsky. Ann. de l'Inst. Fourier 18 (1968), 339–456.
Schützenberger, M. P.: Sur les relations rationnelles entre monodes libres. Theoretical Computer Science 3, 2 (1976), 243–259.
Turakainen, P.: Transducers and compositions of morphisms and inverse morphisms. In Studies in honour of Arto Kustaa Salomaa on the occasion of his fiftieth birthday (1984), vol. 186 of Ann. Univ. Turku. Ser. A I, pp. 118–128.
Wood, D.: Iterated α-NGSM maps and γ systems. Information and Control 32, 1 (1976), 1–26.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Latteux, M., Simplot, D., Terlutte, A. (1998). Iterated length-preserving rational transductions. In: Brim, L., Gruska, J., Zlatuška, J. (eds) Mathematical Foundations of Computer Science 1998. MFCS 1998. Lecture Notes in Computer Science, vol 1450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0055778
Download citation
DOI: https://doi.org/10.1007/BFb0055778
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64827-7
Online ISBN: 978-3-540-68532-6
eBook Packages: Springer Book Archive