Article contents
Iteration of rational transductions
Published online by Cambridge University Press: 15 April 2002
Abstract
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.
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, 2000
References
- 6
- Cited by