Finite-valued Streaming String Transducers

TheoretiCS, vol. Volume 4

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. In this paper, we extend the above results to copyless streaming string transducers (SSTs), answering questions raised by Alur and Deshmukh in 2011. SSTs strictly extend the expressiveness of one-way transducers via additional variables that store partial outputs. We prove that any k-valued SST can be effectively decomposed as a union of k (single-valued) deterministic SSTs. As a corollary, we obtain equivalence of SSTs and two-way transducers in the finite-valued case (those two models are incomparable in general). Another corollary is an elementary upper bound for checking equivalence of finite-valued SSTs. The latter problem was already known to be decidable, but the proof complexity was unknown (it relied on Ehrenfeucht's conjecture). Finally, our main result is that finite valuedness of SSTs is decidable. The complexity is PSpace, and even PTime when the number of variables is fixed. Comment: 36 pages. This is the TheoretiCS journal version. This article is an extended version of the LICS'24 paper by the same name. Updated to correct metadata

Authors 5

1. Emmanuel Filiot

   Université Libre de Bruxelles

   Affiliation as printed

   Université libre de Bruxelles , Belgium

2. Ismaël Jecker
   Affiliation as printed

   Université de Besanc ¸on , France

3. Anca Muscholl

   Université de Bordeaux · Laboratoire Bordelais de Recherche en Informatique

   Affiliation as printed

   LaBRI , Université Bordeaux , France

4. Gabriele Puppis

   University of Udine

   Affiliation as printed

   University of Udine , Italy

5. Sarah Winter

   Université Paris Cité · Institut de Recherche en Informatique Fondamentale

   Affiliation as printed

   IRIF , Université Paris Cité , France