Copyful Streaming String Transducers - Laboratoire d'informatique fondamentale de Marseille
Communication Dans Un Congrès Année : 2017

Copyful Streaming String Transducers

Résumé

Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. ˇ Cern´yCern´y in 2010 as a one-way determin-istic automata model to define transductions of finite strings. Copyless SST extend deterministic finite state automata with a set of variables in which to store intermediate output strings, and those variables can be combined and updated all along the run, in a linear manner, i.e., no variable content can be copied on transitions. It is known that copyless SST capture exactly the class of MSO-definable string-to-string trans-ductions, and are as expressive as deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decid-able equivalence problem (in PSpace). On the other hand, HDT0L systems have been introduced for a while, the most prominent result being the decidability of the equivalence problem. In this paper, we propose a semantics of HDT0L systems in terms of transductions, and use it to study the class of deterministic copyful SST. Our contributions are as follows: (i) HDT0L systems and total deterministic copyful SST have the same expressive power, (ii) the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in linear time. As a consequence, equivalence of deterministic SST is decid-able, (iii) the functionality of non-deterministic copyful SST is decidable, (iv) determining whether a deterministic copyful SST can be transformed into an equivalent deterministic copyless SST is decidable in polynomial time.
Fichier principal
Vignette du fichier
rp17.pdf (320.45 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01782442 , version 1 (02-05-2018)

Identifiants

  • HAL Id : hal-01782442 , version 1

Citer

Emmanuel Filiot, Pierre-Alain Reynier. Copyful Streaming String Transducers. 11th International Workshop on Reachability Problems (RP 2017), Sep 2017, London, United Kingdom. ⟨hal-01782442⟩
174 Consultations
319 Téléchargements

Partager

More