Logics and Automata for Totally Ordered Trees

Marco Kuhlmann 1 Joachim Niehren 2, *
* Auteur correspondant
2 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Totally ordered trees are trees equipped with an additional total order on their nodes. They provide a formal model for data that comes with both a hierarchical and a sequential structure; one example for such data are natural language sentences, where a sequential structure is given by word order, and a hierarchical structure is given by grammatical relations between words. In this paper, we study monadic second"-order logic (MSO) for totally ordered terms. We show that the MSO satisfiability problem of unrestricted structures is undecidable, but give a decision procedure for practically relevant sub"-classes, based on tree automata.
Type de document :
Communication dans un congrès
19th International Conference on Rewriting Techniques and Applications, Jun 2008, Linz, Austria. Springer Verlag, 5117, pp.217-231, 2008, Lecture Notes in Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00610420
Contributeur : Joachim Niehren <>
Soumis le : vendredi 22 juillet 2011 - 01:58:33
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : lundi 12 novembre 2012 - 15:12:28

Fichier

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

Identifiants

  • HAL Id : inria-00610420, version 1

Collections

Citation

Marco Kuhlmann, Joachim Niehren. Logics and Automata for Totally Ordered Trees. 19th International Conference on Rewriting Techniques and Applications, Jun 2008, Linz, Austria. Springer Verlag, 5117, pp.217-231, 2008, Lecture Notes in Computer Science. 〈inria-00610420〉

Partager

Métriques

Consultations de la notice

214

Téléchargements de fichiers

172