| 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. |
Export this paper
