Temporalized logics and automata for time granularity

Details Temporalized logics and automata for time granularity Temporalized logics and automata for time granularity

2003-11-17

arxiv.org/abs/cs/0311022v1

Computer Science

Logic in Computer Science

Journal: Theory and Practice of Logic Programming Journal Acronym: TPLP Category: Paper for Special Issue (Verification and Co

Scientific paper

Suitable extensions of the monadic second-order theory of k successors have been proposed in the literature to capture the notion of time granularity. In this paper, we provide the monadic second-order theories of downward unbounded layered structures, which are infinitely refinable structures consisting of a coarsest domain and an infinite number of finer and finer domains, and of upward unbounded layered structures, which consist of a finest domain and an infinite number of coarser and coarser domains, with expressively complete and elementarily decidable temporal logic counterparts. We obtain such a result in two steps. First, we define a new class of combined automata, called temporalized automata, which can be proved to be the automata-theoretic counterpart of temporalized logics, and show that relevant properties, such as closure under Boolean operations, decidability, and expressive equivalence with respect to temporal logics, transfer from component automata to temporalized ones. Then, we exploit the correspondence between temporalized logics and automata to reduce the task of finding the temporal logic counterparts of the given theories of time granularity to the easier one of finding temporalized automata counterparts of them.

Affiliated with

Also associated with

No associations

Rating

Temporalized logics and automata for time granularity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Temporalized logics and automata for time granularity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Temporalized logics and automata for time granularity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-605285