Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A Hierarchical Completeness Proof for Propositional Interval Temporal Logic with Finite Time

A Hierarchical Completeness Proof for Propositional Interval Temporal Logic with Finite Time We present a completeness proof for Propositional Interval Temporal Logic (PITL) with finite time which avoids certain difficulties of conventional methods. It is more gradated than previous efforts since we progressively reduce reasoning within the original logic to simpler reasoning in sublogics. Furthermore, our approach benefits from being less constructive since it is able to invoke certain theorems about regular languages over finite words without the need to explicitly describe the associated intricate proofs. A modified version of regular expressions called Fusion Expressions is used as part of an intermediate logic called Fusion Logic. Both have the same expressiveness as PITL but are lower-level notations which play an important role in the hierarchical structure of the overall completeness proof. In particular, showing completeness for PITL is reduced to showing completeness for Fusion Logic. This in turn is shown to hold relative to completeness for conventional linear-time temporal logic with finite time. Logics based on regular languages over finite words and !-words offer a promising but elusive framework for formal specification and verification. A number of such logics and decision procedures have been proposed. In addition, various researchers have obtained complete axiom systems by embedding and expressing the decision procedures directly within the logics. The work described here contributes to this topic by showing how to exploit some interesting links between regular languages and interval-based temporal logics. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied Non-Classical Logics Taylor & Francis

A Hierarchical Completeness Proof for Propositional Interval Temporal Logic with Finite Time

Moszkowski, Ben
Journal of Applied Non-Classical Logics , Volume 14 (1-2): 50 – Jan 1, 2004
Download PDF
50 pages

A Hierarchical Completeness Proof for Propositional Interval Temporal Logic with Finite Time

Abstract

We present a completeness proof for Propositional Interval Temporal Logic (PITL) with finite time which avoids certain difficulties of conventional methods. It is more gradated than previous efforts since we progressively reduce reasoning within the original logic to simpler reasoning in sublogics. Furthermore, our approach benefits from being less constructive since it is able to invoke certain theorems about regular languages over finite words without the need to explicitly describe the...
Loading next page...
 
/lp/taylor-francis/a-hierarchical-completeness-proof-for-propositional-interval-temporal-B8qUo1bM1p
Publisher
Taylor & Francis
Copyright
Copyright Taylor & Francis Group, LLC
ISSN
1958-5780
eISSN
1166-3081
DOI
10.3166/jancl.14.55-104
Publisher site
See Article on Publisher Site

Abstract

We present a completeness proof for Propositional Interval Temporal Logic (PITL) with finite time which avoids certain difficulties of conventional methods. It is more gradated than previous efforts since we progressively reduce reasoning within the original logic to simpler reasoning in sublogics. Furthermore, our approach benefits from being less constructive since it is able to invoke certain theorems about regular languages over finite words without the need to explicitly describe the associated intricate proofs. A modified version of regular expressions called Fusion Expressions is used as part of an intermediate logic called Fusion Logic. Both have the same expressiveness as PITL but are lower-level notations which play an important role in the hierarchical structure of the overall completeness proof. In particular, showing completeness for PITL is reduced to showing completeness for Fusion Logic. This in turn is shown to hold relative to completeness for conventional linear-time temporal logic with finite time. Logics based on regular languages over finite words and !-words offer a promising but elusive framework for formal specification and verification. A number of such logics and decision procedures have been proposed. In addition, various researchers have obtained complete axiom systems by embedding and expressing the decision procedures directly within the logics. The work described here contributes to this topic by showing how to exploit some interesting links between regular languages and interval-based temporal logics.

Journal

Journal of Applied Non-Classical Logics – Taylor & Francis

Published: Jan 1, 2004

Keywords: interval temporal logic; completeness proof; fusion product

There are no references for this article.