Minimizing Tree Automata for Unranked Trees

Abstract : Automata for unranked trees form a foundation for XML schemas, querying and pattern languages. We study the problem of efficiently minimizing such automata. We start with the unranked tree automata (UTAs) that are standard in database theory, assuming bottom-up determinism and that horizontal recursion is represented by deterministic finite automata. We show that minimal UTAs in that class are not unique and that minimization is NP-hard. We then study more recent automata classes that do allow for polynomial time minimization. Among those, we show that bottom-up deterministic stepwise tree automata yield the most succinct representations.
Type de document :
Communication dans un congrès
Gavin M. Bierman and Christoph Koch. 10th International Symposium on Database Programming Languages, 2005, Trondheim, Norway. Springer, 3774, pp.232--246, 2005, Lecture Notes in Computer Science
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00536521
Contributeur : Joachim Niehren <>
Soumis le : mardi 16 novembre 2010 - 13:32:06
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 17 février 2011 - 02:57:38

Fichier

mini.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00536521, version 1

Collections

Citation

Wim Martens, Joachim Niehren. Minimizing Tree Automata for Unranked Trees. Gavin M. Bierman and Christoph Koch. 10th International Symposium on Database Programming Languages, 2005, Trondheim, Norway. Springer, 3774, pp.232--246, 2005, Lecture Notes in Computer Science. 〈inria-00536521〉

Partager

Métriques

Consultations de la notice

297

Téléchargements de fichiers

253