Logic of Time Division on Intervals of Finite Size

Tulenheimo, Tero

Document type :

Partie d'ouvrage

Title :

Logic of Time Division on Intervals of Finite Size

Author(s) :

Tulenheimo, Tero [Auteur]
Savoirs, Textes, Langage (STL) - UMR 8163 [STL]

Book title :

Logic of Knowledge - Theory and Applications

Publisher :

College Publications

Publication date :

2012-05-09

English keyword(s) :

finite model theory
formal language theory
division
interval
modal logic
regular language

HAL domain(s) :

Sciences de l'Homme et Société/Philosophie
Mathématiques [math]/Logique [math.LO]

English abstract : [en]

Logic of time division (or TD) was formulated in (Tulenheimo, 2008). It is syntactically like basic modal logic with an additional unary operator but it has an interval-based semantics. The formula is interpreted as meaning ...
Show more >Logic of time division (or TD) was formulated in (Tulenheimo, 2008). It is syntactically like basic modal logic with an additional unary operator but it has an interval-based semantics. The formula is interpreted as meaning 'the current interval has a finite partition of size at least two such that all its members are non-empty and satisfy .' In the present paper the expressive power of TD is studied on the class K_fin of all intervals of finite size. This logic is characterized from the viewpoint of formal language theory by using certain regular-like operators. We prove that TD is not translatable into first-order logic over K_fin. An extension TDN of TD is considered, obtained by making the additional operator 'and next' available. The logic TDN is characterized in terms of regular operators and it is seen to coincide for its expressive power with monadic second-order logic over K_fin. We also study some closure properties of definable classes of intervals in connection with certain fragments of TDN.Show less >

Language :

Anglais

Audience :

Non spécifiée

Popular science :

Non

Collections :