Abstract
Streaming tree transducers with single-use restriction (\(\mathrm {STT}_{\mathrm {sur}}\text {s}\)) were introduced by Alur and D’Antoni as an analyzable, executable, and expressive model for transforming unranked ordered trees in a single pass. The equivalence problem of \(\mathrm {STT}_{\mathrm {sur}}\text {s}\) is decidable because their class is as expressive as the class of MSO-definable tree transformations. In this paper, we present streaming ranked-tree-to-string transducers (\(\mathrm {SRTSTs}\)), based on \(\mathrm {STT}_{\mathrm {sur}}\text {s}\): \(\mathrm {SRTSTs}\) are released from the single-use restriction while their input and output are restricted to ranked trees and strings, respectively. We show that the expressiveness of \(\mathrm {SRTSTs}\) coincides with that of deterministic top-down tree transducers with regular look-ahead (\(\mathrm {yDT}^{\mathrm {R}}\mathrm {s}\)), whose equivalence problem is known to be decidable. Our proof is done by constructing equivalent transducers in both directions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The full version (with full proofs) is found in: http://www.riec.tohoku.ac.jp/~asada/.
- 2.
In the current paper, notions with (resp. without) single-use restriction are written by words with (resp. without) the subscript \({}_{\mathrm {sur}}\) such as \(\mathrm {STT}_{\mathrm {sur}}\) (resp. \(\mathrm {STT}\)). In [1], \(\mathrm {STT}_{\mathrm {sur}}\) and \(\mathrm {STST}_{\mathrm {sur}}\) are written just as \(\mathrm {STT}\) and \(\mathrm {STST}\), respectively.
References
Alur, R., D’Antoni, L.: Streaming tree transducers. J. ACM 64(5), 31:1–31:55 (2017)
Alur, R., Černý, P.: Streaming transducers for algorithmic verification of single-pass list-processing programs. In: POPL 2011, pp. 599–610. ACM (2011)
Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007)
Engelfriet, J.: Top-down tree transducers with regular look-ahead. Math. Syst. Theory 10(1), 289–303 (1976)
Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages. In: Formal Language Theory, pp. 241–286. Academic Press (1980)
Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO definable tree translations. Inform. Comput. 154(1), 34–91 (1999)
Engelfriet, J., Maneth, S.: The equivalence problem for deterministic MSO tree transducers is decidable. Inform. Process. Lett. 100(5), 206–212 (2006)
Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems, and two-way machines. J. Comput. Syst. Sci. 20(2), 150–202 (1980)
Filiot, E., Reynier, P.A.: Copyful streaming string transducers. In: Hague, M., Potapov, I. (eds.) Reachability Problems. LNCS, vol. 10506, pp. 75–86. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67089-8_6
Nakano, K., Mu, S.-C.: A pushdown machine for recursive XML processing. In: Kobayashi, N. (ed.) APLAS 2006. LNCS, vol. 4279, pp. 340–356. Springer, Heidelberg (2006). https://doi.org/10.1007/11924661_21
Seidl, H., Maneth, S., Kemper, G.: Equivalence of deterministic top-down tree-to-string transducers is decidable. In: FOCS 2015, pp. 943–962. IEEE (2015)
Seidl, H., Maneth, S., Kemper, G.: Equivalence of deterministic top-down tree-to-string transducers is decidable. J. ACM 65(4), 21:1–21:30 (2018)
Staworko, S., Laurence, G., Lemay, A., Niehren, J.: Equivalence of deterministic nested word to word transducers. In: FCT 2009. LNCS, vol. 5699, pp. 310–322. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03409-1_28
Acknowledgments
We thank anonymous referees for useful comments. This work was supported by JSPS KAKENHI Grant Numbers JP17K00007, JP17H06099, JP18H04093, and JP18K11156.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Takahashi, Y., Asada, K., Nakano, K. (2019). Streaming Ranked-Tree-to-String Transducers. In: Hospodár, M., Jirásková, G. (eds) Implementation and Application of Automata. CIAA 2019. Lecture Notes in Computer Science(), vol 11601. Springer, Cham. https://doi.org/10.1007/978-3-030-23679-3_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-23679-3_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-23678-6
Online ISBN: 978-3-030-23679-3
eBook Packages: Computer ScienceComputer Science (R0)