Temporal Prepositions and Their Logic Ian Pratt-Hartmann   View Paper (PDF)   Return to Invited Talks Abstract This extended abstract reports on the computational complexity of reasoning with English sentences featuring temporal prepositions. A fragment of English featuring these constructions, called TPE, is defined by means of a context-free grammar. The phrase-structures which this grammar assigns to the sentences it recognizes can be viewed as formulas of an interval temporal logic, called TPL, whose satisfaction-conditions faithfully represent the meanings of the corresponding English sentences. It is shown that the satisfiability problem for TPL is NEXPTIME-complete. BIBTEX @inproceedings{DBLP:conf/time/Pratt-Hartmann04,    author    = {Ian Pratt-Hartmann},    title     = {Temporal Prepositions and Their Logic.},    booktitle = {TIME},    year      = {2004},    pages     = {7-8},    ee        = {http://csdl.computer.org/comp/proceedings/time/2004/2155/00/21550007abs.htm},    crossref  = {conf/time/2004},    bibsource = {DBLP, http://dblp.uni-trier.de}  }  @proceedings{DBLP:conf/time/2004,    title     = {11th International Symposium on Temporal Representation                 and Reasoning (TIME 2004), 1-3 July 2004, Tatihou Island,                 Normandie, France},    booktitle = {TIME},    publisher = {IEEE Computer Society},    year      = {2004},    isbn      = {0-7695-2155-X},    bibsource = {DBLP, http://dblp.uni-trier.de}  } }, ©2005 Association for Computing Machinery