Lecture Notes in Computer Science, 2008, Volume 5257/2008, 491-503, DOI: 10.1007/978-3-540-85780-8_39

Construction of Tree Automata from Regular Expressions

Dietrich Kuske and Ingmar Meinecke

View Related Documents

Abstract

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.

Fulltext Preview

Image of the first page of the fulltext document