Taxonomies of regular tree algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

Algorithms for acceptance, pattern matching and parsing of regular trees and the tree automata used in these algorithms have many applications, including instruction selection in compilers, implementation of term rewriting systems, and model checking. Many such tree algorithms and constructions for such tree automata appear in the literature, but some deficiencies existed, including: inaccessibility of theory and algorithms; difficulty of comparing algorithms due to variations in presentation style and level of formality; and lack of reference to the theory in many publications. An algorithm taxonomy is an effective means of bringing order to such a field. We report on two taxonomies of regular tree algorithms that we have constructed to deal with the deficiencies. The complete work has been presented in the PhD thesis of the first author.
LanguageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009)
EditorsJ. Holub, J. Zdarek
Place of PublicationPrague
PublisherCzech Technical University in Prague
Pages146-159
ISBN (Print)978-80-01-04403-2
StatePublished - 2009

Fingerprint

Trees (mathematics)
Taxonomies
Pattern matching
Model checking

Cite this

Cleophas, L. G. W. A., & Hemerik, C. (2009). Taxonomies of regular tree algorithms. In J. Holub, & J. Zdarek (Eds.), Proceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009) (pp. 146-159). Prague: Czech Technical University in Prague.
Cleophas, L.G.W.A. ; Hemerik, C./ Taxonomies of regular tree algorithms. Proceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009). editor / J. Holub ; J. Zdarek. Prague : Czech Technical University in Prague, 2009. pp. 146-159
@inproceedings{6e82dbdf634940cc922d82e404eecdbd,
title = "Taxonomies of regular tree algorithms",
abstract = "Algorithms for acceptance, pattern matching and parsing of regular trees and the tree automata used in these algorithms have many applications, including instruction selection in compilers, implementation of term rewriting systems, and model checking. Many such tree algorithms and constructions for such tree automata appear in the literature, but some deficiencies existed, including: inaccessibility of theory and algorithms; difficulty of comparing algorithms due to variations in presentation style and level of formality; and lack of reference to the theory in many publications. An algorithm taxonomy is an effective means of bringing order to such a field. We report on two taxonomies of regular tree algorithms that we have constructed to deal with the deficiencies. The complete work has been presented in the PhD thesis of the first author.",
author = "L.G.W.A. Cleophas and C. Hemerik",
year = "2009",
language = "English",
isbn = "978-80-01-04403-2",
pages = "146--159",
editor = "J. Holub and J. Zdarek",
booktitle = "Proceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009)",
publisher = "Czech Technical University in Prague",
address = "Czech Republic",

}

Cleophas, LGWA & Hemerik, C 2009, Taxonomies of regular tree algorithms. in J Holub & J Zdarek (eds), Proceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009). Czech Technical University in Prague, Prague, pp. 146-159.

Taxonomies of regular tree algorithms. / Cleophas, L.G.W.A.; Hemerik, C.

Proceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009). ed. / J. Holub; J. Zdarek. Prague : Czech Technical University in Prague, 2009. p. 146-159.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Taxonomies of regular tree algorithms

AU - Cleophas,L.G.W.A.

AU - Hemerik,C.

PY - 2009

Y1 - 2009

N2 - Algorithms for acceptance, pattern matching and parsing of regular trees and the tree automata used in these algorithms have many applications, including instruction selection in compilers, implementation of term rewriting systems, and model checking. Many such tree algorithms and constructions for such tree automata appear in the literature, but some deficiencies existed, including: inaccessibility of theory and algorithms; difficulty of comparing algorithms due to variations in presentation style and level of formality; and lack of reference to the theory in many publications. An algorithm taxonomy is an effective means of bringing order to such a field. We report on two taxonomies of regular tree algorithms that we have constructed to deal with the deficiencies. The complete work has been presented in the PhD thesis of the first author.

AB - Algorithms for acceptance, pattern matching and parsing of regular trees and the tree automata used in these algorithms have many applications, including instruction selection in compilers, implementation of term rewriting systems, and model checking. Many such tree algorithms and constructions for such tree automata appear in the literature, but some deficiencies existed, including: inaccessibility of theory and algorithms; difficulty of comparing algorithms due to variations in presentation style and level of formality; and lack of reference to the theory in many publications. An algorithm taxonomy is an effective means of bringing order to such a field. We report on two taxonomies of regular tree algorithms that we have constructed to deal with the deficiencies. The complete work has been presented in the PhD thesis of the first author.

M3 - Conference contribution

SN - 978-80-01-04403-2

SP - 146

EP - 159

BT - Proceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009)

PB - Czech Technical University in Prague

CY - Prague

ER -

Cleophas LGWA, Hemerik C. Taxonomies of regular tree algorithms. In Holub J, Zdarek J, editors, Proceedings of the Prague Stringology Conference 2009 (PSC'09, Prague, Czech Republic, August 31-September 2, 2009). Prague: Czech Technical University in Prague. 2009. p. 146-159.