Logics and Automata for Totally Ordered Trees
2008 (English)In: Rewriting Techniques and Applications, Proceedings / [ed] Voronkov, A, Springer Berlin/Heidelberg, 2008, 217-231 p.Conference paper (Refereed)
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
Springer Berlin/Heidelberg, 2008. 217-231 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 5117
Language Technology (Computational Linguistics)
Research subject Computational Linguistics
IdentifiersURN: urn:nbn:se:liu:diva-100286DOI: 10.1007/978-3-540-70590-1_15ISI: 000258327800015ISBN: 978-3-540-70588-8 (print)ISBN: 978-3-540-70590-1 (online)OAI: oai:DiVA.org:liu-100286DiVA: diva2:661498
19th International Conference on Rewriting Techniques and Applications Res Inst Symbol Computat, Hagenberg, AUSTRIA, JUL 15-17, 2008