Right Propositional Neighborhood Logic over Natural Numbers with Integer Constraints for Interval Lengths

Interval temporal logics are based on interval structures over linearly (or partially) ordered domains, where time intervals, rather than time instants, are the primitive ontological entities. In this paper we introduce and study Right Propositional Neighborhood Logic over natural numbers with integ...

Full description

Saved in:
Bibliographic Details
Main Authors: Bresolin, D., Goranko, V., Montanari, A., Sciavicco, G.
Format: Conference Proceeding
Language:English
Subjects:
Artificial intelligence
Calculus
Computer science
Constraint theory
Logic
Natural language processing
Ontologies
Real time systems
Software engineering
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Interval temporal logics are based on interval structures over linearly (or partially) ordered domains, where time intervals, rather than time instants, are the primitive ontological entities. In this paper we introduce and study Right Propositional Neighborhood Logic over natural numbers with integer constraints for interval lengths, which is a propositional interval temporal logic featuring a modality for the 'right neighborhood' relation between intervals and explicit integer constraints for interval lengths. We prove that it has the bounded model property with respect to ultimately periodic models and is therefore decidable. In addition, we provide an EXP SPACE procedure for satisfiability checking and we prove EXPSPACE-hardness by a reduction from the exponential corridor tiling problem.
ISSN:1551-0255
2160-7656
DOI:10.1109/SEFM.2009.36