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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00536694
Contributor : Iovka Boneva <>
Submitted on : Tuesday, November 16, 2010 - 5:32:09 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Thursday, February 17, 2011 - 3:07:08 AM

File

rta2005.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00536694, version 1

Collections

Citation

Iovka Boneva, Jean-Marc Talbot. Automata and Logics for Unranked and Unordered Trees. 20th International Conference on Rewriting Techniques and Applications, 2005, Nara, Japan. pp.500--515. ⟨inria-00536694⟩

Share

Metrics

Record views

246

Files downloads

372