Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-70590-1_15 | RTA |
Keywords | Field | DocType |
mso satisfiability problem,word order,unrestricted structure,decision procedure,sequential structure,hierarchical structure,grammatical relation,additional total order,tree automaton,formal model,computational linguistics,satisfiability,natural language,total order | Discrete mathematics,Word order,Computer science,Automaton,Computational linguistics,Boolean satisfiability problem,Algorithm,Natural language,Tree structure,Monad (functional programming),Undecidable problem | Conference |
Volume | ISSN | Citations |
5117 | 0302-9743 | 1 |
PageRank | References | Authors |
0.34 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marco Kuhlmann | 1 | 309 | 23.06 |
| Joachim Niehren | 2 | 971 | 66.53 |