We consider a new fragment of first-order logic with two variables. This logic is defined over interval structures. It constitutes unary predicates, a binary predicate and a function symbol. Considering such a fragment of first-order logic is motivated by defining a general framework for event-based interval temporal logics. In this paper, we present a sound, complete and terminating decision procedure for this logic. We show that the logic is decidable, and provide a NEXPTIME complexity bound for satisfiability. This result shows (...) that even a simple decidable fragment of first-order logic has NEXPTIME complexity. (shrink)

Logics of discrete time are, in Arthur Prior’s words, “applicable in limited fields of discourse in which we are concerned with what happens in a sequence of discrete states,” independent of “any serious metaphysical assumption that time is discrete.” This insight is applied to natural language semantics, a widespread assumption in which is that time is, as is the real line, dense. “Limited fields of discourse” are construed as finite sets of temporal propositions, inducing bounded notions of temporal granularity that (...) can be refined to expand the discourse. The construal is developed in line with Prior’s view of what is “metaphysically fundamental”. (shrink)

Intervals and the events that occur in them are encoded as strings, elaborating on a conception of events as “intervals cum description.” Notions of satisfaction in interval temporal logics are formulated in terms of strings, and the possibility of computing these via finite-state machines/transducers is investigated. This opens up temporal semantics to finite-state methods, with entailments that are decidable insofar as these can be reduced to inclusions between regular languages.