Undecidability and temporal logic: some landmarks from Turing to the present

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

View graph of relations

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 languageEnglish
Title2012 19th International Symposium on Temporal Representation and Reasoning (TIME)
Publication date2012
Pages3-4
ISBN (print)978-1-4673-2659-9
DOIs
StatePublished

Conference

Conference19th International Symposium on Temporal Representation and Reasoning (TIME 2012)
CountryUnited Kingdom
CityLeicester
Period12/09/1214/09/12
Internet addresshttp://www.tech.dmu.ac.uk/STRL/time12/
CitationsWeb of Science® Times Cited: No match on DOI

Keywords

  • Temporal logics, Undecidability, Halting problem
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 12516363