Skip to Main content Skip to Navigation
Conference papers

Copyful Streaming String Transducers

Emmanuel Filiot 1 Pierre-Alain Reynier 2, 3
2 MOVE - Modélisation et Vérification
LIF - Laboratoire d'informatique Fondamentale de Marseille
3 MOVE - Modélisation et Vérification
LIS - Laboratoire d'Informatique et Systèmes
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01782442
Contributor : Pierre-Alain Reynier <>
Submitted on : Wednesday, May 2, 2018 - 11:08:19 AM
Last modification on : Thursday, June 4, 2020 - 10:40:07 AM
Document(s) archivé(s) le : Monday, September 24, 2018 - 7:09:01 PM

File

rp17.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01782442, version 1

Collections

Citation

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

Share

Metrics

Record views

181

Files downloads

285