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

Valentin Goranko

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    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 languageEnglish
    Title of host publication2012 19th International Symposium on Temporal Representation and Reasoning (TIME)
    Publication date2012
    Pages3-4
    ISBN (Print)978-1-4673-2659-9
    DOIs
    Publication statusPublished - 2012
    Event19th International Symposium on Temporal Representation and Reasoning (TIME 2012) - Leicester, United Kingdom
    Duration: 12 Sep 201214 Sep 2012
    http://www.tech.dmu.ac.uk/STRL/time12/

    Conference

    Conference19th International Symposium on Temporal Representation and Reasoning (TIME 2012)
    Country/TerritoryUnited Kingdom
    CityLeicester
    Period12/09/201214/09/2012
    Internet address

    Keywords

    • Temporal logics
    • Undecidability
    • Halting problem

    Fingerprint

    Dive into the research topics of 'Undecidability and temporal logic: some landmarks from Turing to the present'. Together they form a unique fingerprint.

    Cite this