One-way Definability of Sweeping Transducer

Baschenis, Félix; Gauwin, Olivier; Muscholl, Anca; Puppis, Gabriele

doi:10.4230/LIPIcs.FSTTCS.2015.178

File

LIPIcs.FSTTCS.2015.178.pdf

Filesize: 0.58 MB
14 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2015.178
URN: urn:nbn:de:0030-drops-56297

Author Details

Félix Baschenis

Olivier Gauwin

Anca Muscholl

Gabriele Puppis

Cite AsGet BibTex

Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. One-way Definability of Sweeping Transducer. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 178-191, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.178

Abstract

Two-way finite-state transducers on words are strictly more expressive than one-way transducers. It has been shown recently how to decide if a two-way functional transducer has an equivalent one-way transducer, and the complexity of the algorithm is non-elementary. We propose an alternative and simpler characterization for sweeping functional transducers, namely, for transducers that can only reverse their head direction at the extremities of the input. Our algorithm works in 2EXPSPACE and, in the positive case, produces an equivalent one-way transducer of doubly exponential size. We also show that the bound on the size of the transducer is tight, and that the one-way definability problem is undecidable for (sweeping) non-functional transducers.

Keywords

Regular word transductions
sweeping transducers
one-way definability

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Rajeev Alur and Pavol Cerný. Streaming transducers for algorithmic verification of single-pass list-processing programs. In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 599-610. ACM, 2011.
Rajeev Alur, Antoine Durand-Gasselin, and Ashutosh Trivedi. From monadic second-order definable string transformations to transducers. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, (LICS), pages 458-467. IEEE Computer Society, 2013.
Mikolaj Bojańczyk. Transducers with origin information. In Proceedings of the 41st International Colloquium, ICALP 2014, LNCS, pages 26-37. Springer, 2014.
Olivier Carton and Luc Dartois. Aperiodic two-way transducers and FO-transductions. In 24th EACSL Annual Conference on Computer Science Logic (CSL), LIPIcs, pages 160-174. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2(2):216-254, April 2001.
Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais. From two-way to one-way finite state transducers. In 28th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 468-477. IEEE Computer Society, 2013.
Emmanuel Filiot, Shankara Narayanan Krishna, and Ashutosh Trivedi. First-order definable string transformations. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), volume 29 of LIPIcs, pages 147-159, 2014.
M Lothaire. Combinatorics on words. Cambridge University Press, 1997.
Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114-125, 1959.
J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959.