Two variables and two successors
| Authors | |
|---|---|
| Publication date | 2010 |
| Host editors |
|
| Book title | Mathematical Foundations of Computer Science 2010 |
| Book subtitle | 35th international symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010 : proceedings |
| ISBN |
|
| ISBN (electronic) |
|
| Series | Lecture Notes in Computer Science |
| Event | 35th International Symposium on the Mathematical Foundations of Computer Science (MFCS 2010), Brno, Czech Republic |
| Pages (from-to) | 513-524 |
| Publisher | Berlin: Springer |
| Organisations |
|
| Abstract | We look at the finite satisfiability problem of the two variable fragment of first order logic with the successors of two linear orders. While the logic with both the successors and their transitive closures remains undecidable, we prove that the logic with only the successors is decidable. |
| Document type | Conference contribution |
| Language | English |
| Published at |
https://doi.org/10.1007/978-3-642-15155-2_45
(Final published version)
|
| Permalink to this page | |