Closure under union and composition of iterated rational transductions

¹ URA 369 du CNRS, LIFL, Université de Lille I, bâtiment M3, Cité Scientifique, 59655 Villeneuve-d'Ascq Cedex, France; (simplot@lifl.fr)
² URA 369 du CNRS, LIFL, Université de Lille I, bâtiment M3, Cité Scientifique, 59655 Villeneuve-d'Ascq Cedex, France; (terlutte@lifl.fr)

Received: April 1999
Accepted: 26 June 2000

Abstract

We proceed our work on iterated transductions by studying the closure under union and composition of some classes of iterated functions. We analyze this closure for the classes of length-preserving rational functions, length-preserving subsequential functions and length-preserving sequential functions with terminal states. All the classes we obtain are equal. We also study the connection with deterministic context-sensitive languages.

Résumé

Nous poursuivons notre étude des transductions itérées. Dans cet article, nous étudions la cloture par union et composition de quelques classes de fonctions itérées. Nous considérons les fonctions rationnelles, les fonctions sous-séquentielles et les fonctions séquentielles avec états terminaux, et plus particulièrement, celles préservant les longueurs. Toutes les classes de transductions obtenues sont égales et sont en relation étroite avec les langages contextuels déterministes.