Iteration of rational transductions
Iteration of rational transductions
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...
Composed figures of pixels and inverse monoid. (Figures composées de pixels et monoïde inversif.)
Page 1