Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T18:46:12.263Z Has data issue: false hasContentIssue false

Iteration of rational transductions

Published online by Cambridge University Press:  15 April 2002

Alain Terlutte
Affiliation:
UPRESA 8022 du CNRS, LIFL, Université de Lille I, bâtiment M3, Cité Scientifique, 59655 Villeneuve-d'Ascq Cedex, France; (terlutte@lifl.fr)
David Simplot
Affiliation:
UPRESA 8022 du CNRS, LIFL, Université de Lille I, bâtiment M3, Cité Scientifique, 59655 Villeneuve-d'Ascq Cedex, France; (simplot@lifl.fr)
Get access

Abstract

The purpose of this paper is to show connections between iteratedlength-preserving rational transductions and linear spacecomputations. Hence, we study the smallest family of transductions containing length-preserving rational transductions and closed underunion, composition and iteration. We give several characterizations ofthis class using restricted classes of length-preserving rationaltransductions, by showing the connections with "context-sensitivetransductions" and transductions associated with recognizable picturelanguages.

Keywords

Information

Type
Research Article
Copyright
© EDP Sciences, 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable