uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Logics and Automata for Totally Ordered Trees
Uppsala University, Disciplinary Domain of Humanities and Social Sciences, Faculty of Languages, Department of Linguistics and Philology. (Datorlingvistik)ORCID iD: 0000-0002-2492-9872
INRIA Lille Nord Europe.
2008 (English)In: Rewriting Techniques and Applications, Proceedings / [ed] Voronkov, A, 2008, 217-231 p.Conference paper (Refereed)
Abstract [en]

A totally ordered tree is a tree equipped with an additional total order on its nodes. It provides 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.

Place, publisher, year, edition, pages
2008. 217-231 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5117
National Category
Language Technology (Computational Linguistics)
Research subject
Computational Linguistics
URN: urn:nbn:se:uu:diva-17605DOI: 10.1007/978-3-540-70590-1_15ISI: 000258327800015ISBN: 978-3-540-70588-8OAI: oai:DiVA.org:uu-17605DiVA: diva2:45376
19th International Conference on Rewriting Techniques and Applications Res Inst Symbol Computat, Hagenberg, AUSTRIA, JUL 15-17, 2008
Available from: 2008-07-17 Created: 2008-07-17 Last updated: 2013-07-17

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Kuhlmann, Marco
By organisation
Department of Linguistics and Philology
Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 151 hits
ReferencesLink to record
Permanent link

Direct link