Abstract
This is a selective survey and discussion of some of the landmark undecidability results in temporal logic, beginning with Turing's undecidability of the Halting problem which, in retrospect, can be regarded as the historically first undecidability result for a suitable temporal logic over configuration graphs of Turing machines. I will discuss some of the natural habitats of undecidable temporal logics, such as first-order, interval-based and real time temporal logics, as well as some extensions that often lead to undecidability, such as two-dimensional temporal logics and temporal-epistemic logics.
| Original language | English |
|---|---|
| Title of host publication | 2012 19th International Symposium on Temporal Representation and Reasoning (TIME) |
| Publication date | 2012 |
| Pages | 3-4 |
| ISBN (Print) | 978-1-4673-2659-9 |
| DOIs | |
| Publication status | Published - 2012 |
| Event | 19th International Symposium on Temporal Representation and Reasoning (TIME 2012) - Leicester, United Kingdom Duration: 12 Sept 2012 → 14 Sept 2012 http://www.tech.dmu.ac.uk/STRL/time12/ |
Conference
| Conference | 19th International Symposium on Temporal Representation and Reasoning (TIME 2012) |
|---|---|
| Country/Territory | United Kingdom |
| City | Leicester |
| Period | 12/09/2012 → 14/09/2012 |
| Internet address |
Keywords
- Temporal logics
- Undecidability
- Halting problem