Temporal prepositions and their logic

Ian Pratt-Hartmann

doi:10.1016/j.artint.2005.04.003

Temporal prepositions and their logic

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English
Pages (from-to)	1-36
Number of pages	35
Journal	Artificial Intelligence
Volume	166
Issue number	1-2
DOIs	https://doi.org/10.1016/j.artint.2005.04.003
Publication status	Published - Aug 2005

Keywords

Computational complexity
Interval temporal logic
Natural language
Temporal prepositions

Access to Document

10.1016/j.artint.2005.04.003

Cite this

@article{77182240ebe74d54ad2dee34694d783e,

title = "Temporal prepositions and their logic",

abstract = "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. {\textcopyright} 2005 Elsevier B.V. All rights reserved.",

keywords = "Computational complexity, Interval temporal logic, Natural language, Temporal prepositions",

author = "Ian Pratt-Hartmann",

year = "2005",

month = aug,

doi = "10.1016/j.artint.2005.04.003",

language = "English",

volume = "166",

pages = "1--36",

journal = "Artificial Intelligence",

issn = "0004-3702",

publisher = "Elsevier BV",

number = "1-2",

}

TY - JOUR

T1 - Temporal prepositions and their logic

AU - Pratt-Hartmann, Ian

PY - 2005/8

Y1 - 2005/8

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Interval temporal logic

KW - Natural language

KW - Temporal prepositions

U2 - 10.1016/j.artint.2005.04.003

DO - 10.1016/j.artint.2005.04.003

M3 - Article

SN - 0004-3702

VL - 166

SP - 1

EP - 36

JO - Artificial Intelligence

JF - Artificial Intelligence

IS - 1-2

ER -

Temporal prepositions and their logic

Abstract

Keywords

Access to Document

Fingerprint

Cite this