The propositional logic of temporal neighborhood (PNL) features two modalities that make it possible to access intervals adjacent to the right and to the left of the current one. PNL has been extensively studied in the last years. In particular, decidability and complexity of its satisfiability problem have been systematically investigated, and optimal decision procedures have been developed, for various (classes of) linear orders, including N, Z, and Q. The only missing piece is that for R. It is possible to show that PNL is expressive enough to separate Q and R. Unfortunately, there is no way to reduce the satisfiability problem for PNL over R to that over Q. In this paper, we first prove the NEXPTIME-completeness of the satisfiability problem for PNL over R, and then we devise an optimal tableau system for it.
An Optimal Tableau System for the Logic of Temporal Neighborhood over the Reals
SALA, Pietro
2012-01-01
Abstract
The propositional logic of temporal neighborhood (PNL) features two modalities that make it possible to access intervals adjacent to the right and to the left of the current one. PNL has been extensively studied in the last years. In particular, decidability and complexity of its satisfiability problem have been systematically investigated, and optimal decision procedures have been developed, for various (classes of) linear orders, including N, Z, and Q. The only missing piece is that for R. It is possible to show that PNL is expressive enough to separate Q and R. Unfortunately, there is no way to reduce the satisfiability problem for PNL over R to that over Q. In this paper, we first prove the NEXPTIME-completeness of the satisfiability problem for PNL over R, and then we devise an optimal tableau system for it.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
