RAIRO - Theoretical Informatics and Applications

Research Article

Closure under union and composition of iterated rational transductions

D. Simplota1 and A. Terluttea2

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

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

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.

(Received April 1999)

(Accepted June 26 2000)

(Online publication April 15 2002)

Key Words:

  • Rational transductions;
  • rational functions;
  • iteration of transductions;
  • context-sensitive languages.

Mathematics Subject Classification:

  • 68Q45;
  • 68Q42;
  • 68Q70
Metrics