Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders

Dario Della Monica; Valentin Goranko; Guido Sciavicco

doi:10.1016/j.entcs.2011.06.009

Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders

Dario Della Monica
, Valentin Goranko
, Guido Sciavicco

University of Udine
University of Murcia

Research output: Contribution to journal › Conference article › Research › peer-review

Abstract

We investigate the question of how much hybrid machinery can be added to the interval neighbourhood logic PNL and its metric extension MPNL without losing the decidability of their satisfiability problem in N. In particular, we consider the natural hybrid extension of MPNL obtained by adding binders on integer variables ranging over lengths of intervals, thus enabling storage of the length of the current interval undecidable, which is somewhat surprising, being in contrast with the decidability of MPNL, which can be seen as a hybrid language with length constraints only involving constants over interval lengths. These results show that MPNL itself is, in this sense, a maximal decidable (weakly) hybrid extension of PNL. © 2011 Elsevier B.V. All rights reserved.

Original language	English
Journal	Electronic Notes in Theoretical Computer Science
Volume	273
Issue number	1
Pages (from-to)	3-19
ISSN	1571-0661
DOIs	https://doi.org/10.1016/j.entcs.2011.06.009
Publication status	Published - 2011
Event	International Workshop on Hybrid Logic and Applications - Edinburgh, United Kingdom Duration: 10 Jul 2010 → … http://hylocore.ruc.dk/HyLo2010.html

Workshop

Workshop	International Workshop on Hybrid Logic and Applications
Country/Territory	United Kingdom
City	Edinburgh
Period	10/07/2010 → …
Internet address	http://hylocore.ruc.dk/HyLo2010.html

Access to Document

10.1016/j.entcs.2011.06.009

http://hylocore.ruc.dk/HyLo2010.html

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{4818b901f87846d4ae81a3d596fc00d3,

title = "Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders",

abstract = "We investigate the question of how much hybrid machinery can be added to the interval neighbourhood logic PNL and its metric extension MPNL without losing the decidability of their satisfiability problem in N. In particular, we consider the natural hybrid extension of MPNL obtained by adding binders on integer variables ranging over lengths of intervals, thus enabling storage of the length of the current interval undecidable, which is somewhat surprising, being in contrast with the decidability of MPNL, which can be seen as a hybrid language with length constraints only involving constants over interval lengths. These results show that MPNL itself is, in this sense, a maximal decidable (weakly) hybrid extension of PNL. {\textcopyright} 2011 Elsevier B.V. All rights reserved.",

author = "\{Della Monica\}, Dario and Valentin Goranko and Guido Sciavicco",

year = "2011",

doi = "10.1016/j.entcs.2011.06.009",

language = "English",

volume = "273",

pages = "3--19",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier",

number = "1",

note = "International Workshop on Hybrid Logic and Applications, HyLo 2010 ; Conference date: 10-07-2010",

url = "http://hylocore.ruc.dk/HyLo2010.html",

}

TY - GEN

T1 - Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders

AU - Della Monica, Dario

AU - Goranko, Valentin

AU - Sciavicco, Guido

PY - 2011

Y1 - 2011

N2 - We investigate the question of how much hybrid machinery can be added to the interval neighbourhood logic PNL and its metric extension MPNL without losing the decidability of their satisfiability problem in N. In particular, we consider the natural hybrid extension of MPNL obtained by adding binders on integer variables ranging over lengths of intervals, thus enabling storage of the length of the current interval undecidable, which is somewhat surprising, being in contrast with the decidability of MPNL, which can be seen as a hybrid language with length constraints only involving constants over interval lengths. These results show that MPNL itself is, in this sense, a maximal decidable (weakly) hybrid extension of PNL. © 2011 Elsevier B.V. All rights reserved.

AB - We investigate the question of how much hybrid machinery can be added to the interval neighbourhood logic PNL and its metric extension MPNL without losing the decidability of their satisfiability problem in N. In particular, we consider the natural hybrid extension of MPNL obtained by adding binders on integer variables ranging over lengths of intervals, thus enabling storage of the length of the current interval undecidable, which is somewhat surprising, being in contrast with the decidability of MPNL, which can be seen as a hybrid language with length constraints only involving constants over interval lengths. These results show that MPNL itself is, in this sense, a maximal decidable (weakly) hybrid extension of PNL. © 2011 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.entcs.2011.06.009

DO - 10.1016/j.entcs.2011.06.009

M3 - Conference article

SN - 1571-0661

VL - 273

SP - 3

EP - 19

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

IS - 1

T2 - International Workshop on Hybrid Logic and Applications

Y2 - 10 July 2010

ER -

Hybrid Metric Propositional Neighborhood Logics with Interval Length Binders

Abstract

Workshop

Access to Document

OpenUrl availability

Fingerprint

Cite this