Abstract:
Studying the algorithmic properties of interval extensions of dense linear orders, in particular, the complexity degrees (namely, the $s\Sigma$-degree) of the extensions, we show that continuity is a necessary and sufficient condition for the equality between the complexity degrees of an order and its interval extension. We treat temporal approximation spaces over interval extensions as mathematical models of verb semantics in natural languages. We show that the continuity of order implies the effectiveness of checking the validity of $\Delta_0^{DL}$-formulas in spaces over $sc$-simple enrichments. As a corollary, we obtain an effective description of the intervals corresponding to various verb tenses in English.
Keywords:effective model theory, linear order, interval extension, approximation space, mathematical linguistics.