Conference paper
The dark side of Interval Temporal Logic: sharpening the undecidability border
Unlike the Moon, the dark side of interval temporal logics is the one we usually see: their ubiquitous undesirability. Identifying minimal undecidable interval logics is thus a natural and important issue in the research agenda in the area. The decidability status of a logic often depends on the class of models (in our case, the class of interval structures)in which it is interpreted.
In this paper, we have identified several new minimal undecidable logics amongst the fragments of Halpern-Shoham logic HS, including the logic of the overlaps relation, over the classes of all and finite linear orders, as well as the logic of the meet and subinterval relations, over the class of dense linear orders.
Together with previous undecid ability results, this work contributes to delineate the border of the dark side of interval temporal logics quite sharply.
Language: | English |
---|---|
Year: | 2011 |
Pages: | 131-138 |
Proceedings: | 18th International Symposium on Temporal Representation and Reasoning |
ISBN: | 1457712423 and 9781457712425 |
ISSN: | 23326468 and 15301311 |
Types: | Conference paper |
DOI: | 10.1109/TIME.2011.21 |
Cognition Computer science Educational institutions Electronic mail Encoding Halpern-Shoham logic HS Semantics Tiles decidability decidability status dense linear order finite linear order interval logic minimal undecidable interval temporal logic minimal undecidable logic overlap relation subinterval relation temporal logic ubiquitous undecidability undecidability