Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T10:36:26.403Z Has data issue: false hasContentIssue false

Construction of tree automata from regular expressions

Published online by Cambridge University Press:  22 August 2011

Dietrich Kuske
Affiliation:
Fachgebiet Theoretische Informatik, Technische Universität Ilmenau, Postfach 100565, 98684 Ilmenau, Germany. dietrich.kuske@tu-ilmenau.de
Ingmar Meinecke
Affiliation:
Institut für Informatik, Universität Leipzig, PF 100920, 04009 Leipzig, Germany. meinecke@informatik.uni-leipzig.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and Ziadi from words to trees.

Information

Type
Research Article
Copyright
© EDP Sciences, 2011