Finite-valued Streaming String Transducers

Proceedings - Symposium on Logic in Computer Science, pp. 1–14

Abstract

A transducer is finite-valued if for some bound k, it maps any given input to at most k outputs. For classical, one-way transducers, it is known since the 80s that finite valuedness entails decidability of the equivalence problem. This decidability result is in contrast to the general case, which makes finite-valued transducers very attractive. For classical transducers it is also known that finite valuedness is decidable and that any k-valued finite transducer can be decomposed as a union of k single-valued finite transducers.

Authors 6

1. Emmanuel Filiot

   Université Libre de Bruxelles

   Affiliation as printed

   Computer Science, Université Libre de Bruxelles, Brussels, Belgium

2. Ismaël Jecker
   Affiliation as printed

   Université de Besançon, Besançon, France

3. Christof Löding Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

4. Anca Muscholl

   Université de Bordeaux · Laboratoire Bordelais de Recherche en Informatique

   Affiliation as printed

   LaBRI, Universite Bordeaux, Bordeaux, France

5. Gabriele Puppis

   University of Udine

   Affiliation as printed

   Udine University, Udine, Italy

6. Sarah Winter

   Université Paris Cité

   Affiliation as printed

   Université Paris-Cité, Paris, France