Iteration of rational transductions
UPRESA 8022 du CNRS, LIFL, Université de Lille I, bâtiment
M3, Cité Scientifique, 59655 Villeneuve-d'Ascq Cedex, France;
2 UPRESA 8022 du CNRS, LIFL, Université de Lille I, bâtiment M3, Cité Scientifique, 59655 Villeneuve-d'Ascq Cedex, France; (email@example.com)
Accepted: 5 March 2000
The purpose of this paper is to show connections between iterated length-preserving rational transductions and linear space computations. Hence, we study 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 rational transductions, by showing the connections with "context-sensitive transductions" and transductions associated with recognizable picture languages.
Mathematics Subject Classification: 68Q45 / 68Q42 / 68Q70
© EDP Sciences, 2000