Copyful Streaming String Transducers

• Autorzy: Filiot Emmanuel , Reynier Pierre-Alain

Identyfikatory

DOI

10.3233/FI-2021-1998

• Języki publikacji: EN

Abstrakty

EN

Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. Černý in 2010 as a one-way deterministic 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 transductions, and are as expressive as deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decidable 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 quadratic time. As a consequence, equivalence of deterministic SST is decidable, (iii) the functionality of non-deterministic copyful SST is decidable, (iv) determining whether a non-deterministic copyful SST can be transformed into an equivalent non-deterministic copyless SST is decidable in polynomial time.

Słowa kluczowe

EN

equivalence problem; transducers; words

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 178, nr 1/2
• Strony: 59--76
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Filiot Emmanuel

• Université libre de Bruxelles (U.L.B.), Belgium

autor

Reynier Pierre-Alain

• Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France

Bibliografia

• [1] Engelfriet J, Hoogeboom HJ. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2001. 2:216-254. doi:10.1145/371316.371512.
• [2] Engelfriet J, Maneth S. Macro tree transducers, attribute grammars, and MSO definable tree translations. Information and Computation, 1999. 154(1):34-91. URL https://doi.org/10.1006/inco.1999.2807.
• [3] Dartois L, Filiot E, Reynier PA, Talbot JM. Two-Way Visibly Pushdown Automata and Transducers. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’16. ACM, 2016 pp. 217-226. doi:10.1145/2933575.2935315.
• [4] Alur R, Černý P. Expressiveness of streaming string transducers. In: FSTTCS, volume 8. 2010 pp. 1-12. doi:10.4230/LIPIcs.FSTTCS.2010.1.
• [5] Alur R, Filiot E, Trivedi A. Regular Transformations of Infinite Strings. In: LICS. IEEE. 2012 pp. 65-74. ISBN:978-1-4673-2263-8.
• [6] Alur R, D’Antoni L. Streaming Tree Transducers. In: ICALP (2), volume 7392 of LNCS. Springer, 2012 pp. 42-53.
• [7] Alur R, D’Antoni L, Deshmukh JV, Raghothaman M, Yuan Y. Regular Functions and Cost Register Automata. In: 28th Annual ACM/IEEE Symp. on Logic in Computer Science, LICS 2013. IEEE Computer Society. ISBN 978-1-4799-0413-6, 2013 pp. 13-22. doi:10.1109/LICS.2013.65. URL http://doi.ieeecomputersociety.org/10.1109/LICS.2013.65.
• [8] Engelfriet J, Maneth S. The equivalence problem for deterministic MSO tree transducers is decidable. Inf. Process. Lett., 2006. 100(5):206-212.
• [9] Alur A, Černý P. Streaming transducers for algorithmic verification of single-pass list-processing programs. In: POPL. 2011 pp. 599-610.
• [10] Griffiths TV. The Unsolvability of the Equivalence Problem for Lambda-Free Nondeterministic Generalized Machines. J. ACM, 1968. 15(3):409-413. doi:10.1145/321466.321473.
• [11] Alur R, D’Antoni L. Streaming Tree Transducers. CoRR, 2011. abs/1104.2599. URL http://arxiv.org/abs/1104.2599.
• [12] Culik II K, Karhumäki J. The Equivalence of Finite Valued Transducers (On HDT0L Languages) is Decidable. Theor. Comput. Sci., 1986. 47(3):71-84. doi:10.1016/0304-3975(86)90134-9. URL http://dx.doi.org/10.1016/0304-3975(86)90134-9.
• [13] Mandel A, Simon I. On Finite Semigroups of Matrices. Theor. Comput. Sci., 1977. 5(2):101-111.
• [14] Seidl H, Maneth S, Kemper G. Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable. In: IEEE 56th Annual Symp. on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, 2015 pp. 943-962. URL https://doi.org/10.1145/3182653.
• [15] Benedikt M, Duff T, Sharad A, Worrell J. Polynomial automata: Zeroness and applications. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017. 2017 pp. 1-12.
• [16] Alur R, Deshmukh JV. Nondeterministic Streaming String Transducers. In: ICALP, volume 6756 of LNCS. Springer, 2011 pp. 1-20. doi:10.1007/978-3-642-22012-8_1.
• [17] Lindenmayer A. Mathematical models for cellular interaction in development. Journal of Theoretical Biology, 1968. 18:280-315. URL https://doi.org/10.1016/0022-5193(68)90079-9.
• [18] Honkala J. A short solution for the HDT0L sequence equivalence problem. Theor. Comput. Sci., 2000. 244(1-2):267-270. doi:10.1016/S0304-3975(00)00158-4. URL https://doi.org/10.1016/S0304-3975(00)00158-4.
• [19] Filiot E, Reynier PA. Transducers, logic and algebra for functions of finite words. SIGLOG News, 2016. 3(3):4-19. doi:10.1145/2984450.2984453. URL http://doi.acm.org/10.1145/2984450.2984453.
• [20] Engelfriet J, Maneth S. Macro Tree Translations of Linear Size Increase are MSO Definable. SIAM J. Comput., 2003. 32(4):950-1006. doi:10.1137/S0097539701394511.
• [21] Filiot E, Krishna SN, Trivedi A. First-order Definable String Transformations. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, volume 29 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014 pp. 147-159. doi:10.4230/LIPIcs.FSTTCS.2014.147.
• [22] Dartois L, Jecker I, Reynier PA. Aperiodic String Transducers. In: Developments in Language Theory - 20th International Conference, DLT 2016, volume 9840 of Lecture Notes in Computer Science. Springer, 2016 pp. 125-137. arXiv:1506.04059 [cs.FL].
• [23] Weber A, Seidl H. On the Degree of Ambiguity of Finite Automata. Theor. Comput. Sci., 1991. 88(2):325-349. doi:10.1016/0304-3975(91)90381-B.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).