Logics and Automata for Totally Ordered Trees - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2008

Logics and Automata for Totally Ordered Trees

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.
Fichier principal
Vignette du fichier
final.pdf (198.57 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00610420 , version 1 (22-07-2011)

Identifiers

  • HAL Id : inria-00610420 , version 1

Cite

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⟩
145 View
211 Download

Share

Gmail Facebook X LinkedIn More