Copyful Streaming String Transducers - Laboratoire d'informatique fondamentale de Marseille Accéder directement au contenu
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⟩
169 Consultations
308 Téléchargements

Partager

Gmail Facebook X LinkedIn More