Streaming Ranked-Tree-to-String Transducers

Yuta Takahashi; Kazuyuki Asada; Keisuke Nakano

doi:10.1007/978-3-030-23679-3_19

Streaming Ranked-Tree-to-String Transducers

Yuta Takahashi, Kazuyuki Asada, Keisuke Nakano

Systems & Software Division

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

Streaming tree transducers with single-use restriction (STT_surs) 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 STT_surs 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 (SRTSTs), based on STT_surs: 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 SRTSTs coincides with that of deterministic top-down tree transducers with regular look-ahead (yDT^Rs), whose equivalence problem is known to be decidable. Our proof is done by constructing equivalent transducers in both directions.

Original language	English
Title of host publication	Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings
Editors	Michal Hospodár, Galina Jirásková
Publisher	Springer Verlag
Pages	235-247
Number of pages	13
ISBN (Print)	9783030236786
DOIs	https://doi.org/10.1007/978-3-030-23679-3_19
Publication status	Published - 2019
Event	24th International Conference on Implementation and Application of Automata, CIAA 2019 - Košice, Slovakia Duration: 2019 Jul 22 → 2019 Jul 25

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11601 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Implementation and Application of Automata, CIAA 2019
Country/Territory	Slovakia
City	Košice
Period	19/7/22 → 19/7/25

Keywords

Equivalence
Expressiveness
Ranked trees
Streaming transducers

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-23679-3_19

Cite this

Takahashi, Y., Asada, K., & Nakano, K. (2019). Streaming Ranked-Tree-to-String Transducers. In M. Hospodár, & G. Jirásková (Eds.), Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings (pp. 235-247). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11601 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-23679-3_19

Streaming Ranked-Tree-to-String Transducers. / Takahashi, Yuta; Asada, Kazuyuki ; Nakano, Keisuke.
Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. ed. / Michal Hospodár; Galina Jirásková. Springer Verlag, 2019. p. 235-247 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11601 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Takahashi, Y, Asada, K & Nakano, K 2019, Streaming Ranked-Tree-to-String Transducers. in M Hospodár & G Jirásková (eds), Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11601 LNCS, Springer Verlag, pp. 235-247, 24th International Conference on Implementation and Application of Automata, CIAA 2019, Košice, Slovakia, 19/7/22. https://doi.org/10.1007/978-3-030-23679-3_19

Takahashi Y, Asada K , Nakano K. Streaming Ranked-Tree-to-String Transducers. In Hospodár M, Jirásková G, editors, Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. Springer Verlag. 2019. p. 235-247. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-23679-3_19

Takahashi, Yuta ; Asada, Kazuyuki ; Nakano, Keisuke. / Streaming Ranked-Tree-to-String Transducers. Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings. editor / Michal Hospodár ; Galina Jirásková. Springer Verlag, 2019. pp. 235-247 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3d4884221f144e0db75cccde0b4b373c,

title = "Streaming Ranked-Tree-to-String Transducers",

abstract = "Streaming tree transducers with single-use restriction (STTsurs) were introduced by Alur and D{\textquoteright}Antoni as an analyzable, executable, and expressive model for transforming unranked ordered trees in a single pass. The equivalence problem of STTsurs 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 (SRTSTs), based on STTsurs: 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 SRTSTs coincides with that of deterministic top-down tree transducers with regular look-ahead (yDTRs), whose equivalence problem is known to be decidable. Our proof is done by constructing equivalent transducers in both directions.",

keywords = "Equivalence, Expressiveness, Ranked trees, Streaming transducers",

author = "Yuta Takahashi and Kazuyuki Asada and Keisuke Nakano",

note = "Funding Information: Acknowledgments. We thank anonymous referees for useful comments. This work was supported by JSPS KAKENHI Grant Numbers JP17K00007, JP17H06099, JP18H04093, and JP18K11156. Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 24th International Conference on Implementation and Application of Automata, CIAA 2019 ; Conference date: 22-07-2019 Through 25-07-2019",

year = "2019",

doi = "10.1007/978-3-030-23679-3_19",

language = "English",

isbn = "9783030236786",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "235--247",

editor = "Michal Hospod{\'a}r and Galina Jir{\'a}skov{\'a}",

booktitle = "Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings",

}

TY - GEN

T1 - Streaming Ranked-Tree-to-String Transducers

AU - Takahashi, Yuta

AU - Asada, Kazuyuki

AU - Nakano, Keisuke

N1 - Funding Information: Acknowledgments. We thank anonymous referees for useful comments. This work was supported by JSPS KAKENHI Grant Numbers JP17K00007, JP17H06099, JP18H04093, and JP18K11156. Publisher Copyright: © 2019, Springer Nature Switzerland AG.

PY - 2019

Y1 - 2019

N2 - Streaming tree transducers with single-use restriction (STTsurs) 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 STTsurs 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 (SRTSTs), based on STTsurs: 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 SRTSTs coincides with that of deterministic top-down tree transducers with regular look-ahead (yDTRs), whose equivalence problem is known to be decidable. Our proof is done by constructing equivalent transducers in both directions.

AB - Streaming tree transducers with single-use restriction (STTsurs) 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 STTsurs 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 (SRTSTs), based on STTsurs: 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 SRTSTs coincides with that of deterministic top-down tree transducers with regular look-ahead (yDTRs), whose equivalence problem is known to be decidable. Our proof is done by constructing equivalent transducers in both directions.

KW - Equivalence

KW - Expressiveness

KW - Ranked trees

KW - Streaming transducers

UR - http://www.scopus.com/inward/record.url?scp=85069470724&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069470724&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-23679-3_19

DO - 10.1007/978-3-030-23679-3_19

M3 - Conference contribution

AN - SCOPUS:85069470724

SN - 9783030236786

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 235

EP - 247

BT - Implementation and Application of Automata - 24th International Conference, CIAA 2019, Proceedings

A2 - Hospodár, Michal

A2 - Jirásková, Galina

PB - Springer Verlag

T2 - 24th International Conference on Implementation and Application of Automata, CIAA 2019

Y2 - 22 July 2019 through 25 July 2019

ER -

Streaming Ranked-Tree-to-String Transducers

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this