Automata and Logics for Unranked and Unordered Trees

Abstract : In this paper, we consider the monadic second order logic (MSO) and two of its extensions, namely Counting MSO (CMSO) and Presburger MSO (PMSO), interpreted over unranked and unordered trees. We survey classes of tree automata introduced for the logics PMSO and CMSO as well as other related formalisms; we gather results from the literature and sometimes clarify or fill the remaining gaps between those various formalisms. Finally, we complete our study by adapting these classes of automata for capturing precisely the expressiveness of the logic MSO.
Type de document :
Communication dans un congrès
Jürgen Giesl. 20th International Conference on Rewriting Techniques and Applications, 2005, Nara, Japan. Springer, 3467, pp.500--515, 2005, Lecture Notes in Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00536694
Contributeur : Iovka Boneva <>
Soumis le : mardi 16 novembre 2010 - 17:32:09
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 17 février 2011 - 03:07:08

Fichier

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

Identifiants

  • HAL Id : inria-00536694, version 1

Collections

Citation

Iovka Boneva, Jean-Marc Talbot. Automata and Logics for Unranked and Unordered Trees. Jürgen Giesl. 20th International Conference on Rewriting Techniques and Applications, 2005, Nara, Japan. Springer, 3467, pp.500--515, 2005, Lecture Notes in Computer Science. 〈inria-00536694〉

Partager

Métriques

Consultations de la notice

190

Téléchargements de fichiers

217