Temporal prepositions and their logic

    Research output: Contribution to journalArticlepeer-review


    A fragment of English featuring temporal prepositions and the order-denoting adjectives first and last is defined by means of a context-free grammar. The phrase-structures which this grammar assigns to the sentences it recognizes are viewed as formulas of an interval temporal logic, whose satisfaction-conditions faithfully represent the meanings of the corresponding English sentences. It is shown that the satisfiability problem for this logic is NEXPTIME-complete. The computational complexity of determining logical relationships between English sentences featuring the temporal constructions in question is thus established. © 2005 Elsevier B.V. All rights reserved.
    Original languageEnglish
    Pages (from-to)1-36
    Number of pages35
    JournalArtificial Intelligence
    Issue number1-2
    Publication statusPublished - Aug 2005


    • Computational complexity
    • Interval temporal logic
    • Natural language
    • Temporal prepositions


    Dive into the research topics of 'Temporal prepositions and their logic'. Together they form a unique fingerprint.

    Cite this