Computing All Subtree Repeats in Ordered Ranked Trees

Michalis Christou; Maxime Crochemore; Tomas Flouri; Costas S. Iliopoulos; Jan Janousek; Borivoj Melichar; Solon Pissis

doi:10.1007/978-3-642-24583-1_33

Computing All Subtree Repeats in Ordered Ranked Trees

Michalis Christou^*, Maxime Crochemore, Tomas Flouri, Costas S. Iliopoulos, Jan Janousek, Borivoj Melichar, Solon Pissis

^*Corresponding author for this work

Informatics

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

8 Citations (Scopus)

Abstract

We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are cornputed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.

Original language	English
Title of host publication	String Processing and Information Retrieval
Subtitle of host publication	18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings
Editors	R Grossi, F Sebastiani, F Silvestri
Place of Publication	Berlin
Publisher	Springer Berlin Heidelberg
Pages	338-343
Number of pages	6
Volume	N/A
Edition	N/A
ISBN (Print)	9783642245824
DOIs	https://doi.org/10.1007/978-3-642-24583-1_33
Publication status	Published - 2011
Event	18th International Symposium on String Processing and Information Retrieval - Pisa, Italy Duration: 17 Oct 2011 → 21 Oct 2011

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	7024
ISSN (Print)	0302-9743

Conference

Conference	18th International Symposium on String Processing and Information Retrieval
Country/Territory	Italy
City	Pisa
Period	17/10/2011 → 21/10/2011

Keywords

PUSHDOWN-AUTOMATA

Access to Document

10.1007/978-3-642-24583-1_33

Cite this

Christou, M., Crochemore, M., Flouri, T., Iliopoulos, C. S., Janousek, J., Melichar, B., & Pissis, S. (2011). Computing All Subtree Repeats in Ordered Ranked Trees. In R. Grossi, F. Sebastiani, & F. Silvestri (Eds.), String Processing and Information Retrieval: 18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings (N/A ed., Vol. N/A, pp. 338-343). (Lecture Notes in Computer Science; Vol. 7024). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-24583-1_33

Christou, Michalis ; Crochemore, Maxime ; Flouri, Tomas et al. / Computing All Subtree Repeats in Ordered Ranked Trees. String Processing and Information Retrieval: 18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings. editor / R Grossi ; F Sebastiani ; F Silvestri. Vol. N/A N/A. ed. Berlin : Springer Berlin Heidelberg, 2011. pp. 338-343 (Lecture Notes in Computer Science).

@inbook{53a11599a1fe4f4f90f17e89ac8fe220,

title = "Computing All Subtree Repeats in Ordered Ranked Trees",

abstract = "We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are cornputed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.",

keywords = "PUSHDOWN-AUTOMATA",

author = "Michalis Christou and Maxime Crochemore and Tomas Flouri and Iliopoulos, {Costas S.} and Jan Janousek and Borivoj Melichar and Solon Pissis",

year = "2011",

doi = "10.1007/978-3-642-24583-1_33",

language = "English",

isbn = "9783642245824",

volume = "N/A",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "338--343",

editor = "R Grossi and F Sebastiani and F Silvestri",

booktitle = "String Processing and Information Retrieval",

edition = "N/A",

note = "18th International Symposium on String Processing and Information Retrieval ; Conference date: 17-10-2011 Through 21-10-2011",

}

Christou, M , Crochemore, M, Flouri, T, Iliopoulos, CS, Janousek, J, Melichar, B & Pissis, S 2011, Computing All Subtree Repeats in Ordered Ranked Trees. in R Grossi, F Sebastiani & F Silvestri (eds), String Processing and Information Retrieval: 18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings. N/A edn, vol. N/A, Lecture Notes in Computer Science, vol. 7024, Springer Berlin Heidelberg, Berlin, pp. 338-343, 18th International Symposium on String Processing and Information Retrieval, Pisa, Italy, 17/10/2011. https://doi.org/10.1007/978-3-642-24583-1_33

Computing All Subtree Repeats in Ordered Ranked Trees. / Christou, Michalis ; Crochemore, Maxime; Flouri, Tomas et al.
String Processing and Information Retrieval: 18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings. ed. / R Grossi; F Sebastiani; F Silvestri. Vol. N/A N/A. ed. Berlin: Springer Berlin Heidelberg, 2011. p. 338-343 (Lecture Notes in Computer Science; Vol. 7024).

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

TY - CHAP

T1 - Computing All Subtree Repeats in Ordered Ranked Trees

AU - Christou, Michalis

AU - Crochemore, Maxime

AU - Flouri, Tomas

AU - Iliopoulos, Costas S.

AU - Janousek, Jan

AU - Melichar, Borivoj

AU - Pissis, Solon

PY - 2011

Y1 - 2011

N2 - We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are cornputed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.

AB - We consider the problem of finding all subtree repeats in a given ordered ranked tree. Specifically, we transform the given tree to a string representing its postfix notation, and then propose an algorithm based on the bottom-up technique. The proposed algorithm is divided into two phases: the preprocessing phase, and the phase where all subtree repeats are cornputed. The linear runtime of the algorithm, as well as the use of linear auxiliary space, are important aspects of its quality.

KW - PUSHDOWN-AUTOMATA

U2 - 10.1007/978-3-642-24583-1_33

DO - 10.1007/978-3-642-24583-1_33

M3 - Conference paper

SN - 9783642245824

VL - N/A

T3 - Lecture Notes in Computer Science

SP - 338

EP - 343

BT - String Processing and Information Retrieval

A2 - Grossi, R

A2 - Sebastiani, F

A2 - Silvestri, F

PB - Springer Berlin Heidelberg

CY - Berlin

T2 - 18th International Symposium on String Processing and Information Retrieval

Y2 - 17 October 2011 through 21 October 2011

ER -

Christou M , Crochemore M, Flouri T, Iliopoulos CS, Janousek J, Melichar B et al. Computing All Subtree Repeats in Ordered Ranked Trees. In Grossi R, Sebastiani F, Silvestri F, editors, String Processing and Information Retrieval: 18th International Symposium, SPIRE 2011, Pisa, Italy, October 17-21, 2011. Proceedings. N/A ed. Vol. N/A. Berlin: Springer Berlin Heidelberg. 2011. p. 338-343. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-24583-1_33

Computing All Subtree Repeats in Ordered Ranked Trees

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this