Skip to Main content Skip to Navigation
New interface
Conference papers

Logics and Automata for Totally Ordered Trees

Marco Kuhlmann 1 Joachim Niehren 2, * 
* Corresponding author
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Joachim Niehren Connect in order to contact the contributor
Submitted on : Friday, July 22, 2011 - 1:58:33 AM
Last modification on : Friday, February 4, 2022 - 3:17:44 AM
Long-term archiving on: : Monday, November 12, 2012 - 3:12:28 PM


Files produced by the author(s)


  • HAL Id : inria-00610420, version 1



Marco Kuhlmann, Joachim Niehren. Logics and Automata for Totally Ordered Trees. 19th International Conference on Rewriting Techniques and Applications, Jun 2008, Linz, Austria. pp.217-231. ⟨inria-00610420⟩



Record views


Files downloads