Skip to Main content Skip to Navigation
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 metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00610420
Contributor : Joachim Niehren <>
Submitted on : Friday, July 22, 2011 - 1:58:33 AM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on: : Monday, November 12, 2012 - 3:12:28 PM

File

final.pdf
Files produced by the author(s)

Identifiers

  • 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. pp.217-231. ⟨inria-00610420⟩

Share

Metrics

Record views

341

Files downloads

414