Kamp's theorem
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematical logic and computer science, Kamp's theorem states that linear temporal logic is equivalent to the monadic first-order logic of order over the non-negative integers and the real numbers. It is the oldest result in expressive completeness, the study of determining if a given logic can express a desired subject matter.
In temporal logic, a logic \mathcal L is expressive complete if every first-order formula with one free variable is equivalent to a formula in \mathcal L . The theorem was proven by Hans Kamp in his doctoral thesis, Tense Logic and the Theory of Linear Order (1968). In this thesis, Kamp introduces the \mathbf U and \mathbf S operators to Prior's tense logic, increasing its expressive power and ensuring expressive completeness.
Explicitly, Kamp shows that the \mathbf X, \mathbf Y, \mathbf F, \mathbf P operators cannot express \mathbf U .
In mathematical logic and computer science, Kamp's theorem states that linear temporal logic is equivalent to the monadic first-order logic of order over the non-negative integers and the real numbers. It is the oldest result in expressive completeness, the study of determining if a given logic can express a desired subject matter.
In temporal logic, a logic \mathcal L is expressive complete if every first-order formula with one free variable is equivalent to a formula in \mathcal L . The theorem was proven by Hans Kamp in his doctoral thesis, Tense Logic and the Theory of Linear Order (1968). In this thesis, Kamp introduces the \mathbf U and \mathbf S operators to Prior's tense logic, increasing its expressive power and ensuring expressive completeness.
Explicitly, Kamp shows that the \mathbf X, \mathbf Y, \mathbf F, \mathbf P operators cannot express \mathbf U . \varphi ::= \top \mid p \mid \neg \varphi \mid \varphi \land \varphi \mid \mathbf X \varphi \mid \mathbf F \varphi \mid \varphi \mathrel \mathbf U \varphi \mid \mathbf Y \varphi \mid \mathbf P \varphi \mid \varphi \mathrel \mathbf S \varphi An LTL formula is interpreted over a timeline, which is a quadruple \mathcal T = (T, given by a set of times T , a linear order relation on T , a successor relation s such that (t_1, t_2) \in s if t_2 is the successor of t_1 , and an interpretation function \mathcal I : T \to 2^P . This syntax uses the usual \mathbf X and \mathbf U operators, and includes their past duals, \mathbf Y and \mathbf S , respectively. The satisfaction relation \models is defined as follows, where t \in T : \mathcal T, t \models p if p \in \mathcal I(t) \mathcal T, t \models \neg \varphi if \mathcal T, t \not\models \varphi \mathcal T, t \models \varphi \land \psi if \mathcal T, t \models \varphi and \mathcal T, t \models \psi \mathcal T, t \models \mathbf X \varphi if s(t, t + 1) and \mathcal T, t + 1 \models \varphi \mathcal T, t \models \mathbf F \varphi if there is t' \geq t such that \mathcal T, t' \models \varphi \mathcal T, t \models \varphi \mathrel \mathbf U \psi if there is t' \geq t such that \mathcal T, t' \models \psi and \mathcal T, t \models \varphi for all t \in [t, t') \mathcal T, t \models \mathbf Y \varphi if s(t - 1, t) and \mathcal T, t - 1 \models \varphi \mathcal T, t \models \mathbf P \varphi if there is t' \leq t such that \mathcal T, t' \models \varphi \mathcal T, t \models \varphi \mathrel \mathbf S \psi if there is t' \leq t such that \mathcal T, t' \models \psi and \mathcal T, t \models \varphi for all t \in (t', t] The syntax for monadic first-order logic of order (FOMLO) over P is given by the following grammar, where p \in P and first-order variables are denoted by t : \varphi ::= t The standard satisfaction relation is used, where \mathcal T, t \models \varphi(x) denotes that \varphi(t) holds.
Let \mathcal T be a timeline such that T is the natural numbers or the real numbers. Kamp's theorem states that every formula in FOMLO is equivalent to a formula in LTL over \mathcal T . That is, for all FOMLO formulas \varphi(x) , there exists an LTL formula \psi such that for all t \in T , \mathcal T, t \models \varphi(x) \iff \mathcal T, t \models \psi .
The converse direction is given by the standard translation.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1379013815 under CC BY-SA 4.0; modifications have been made.