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.

Hybrid metric propositional neighborhood logics with interval length binders

SCIAVICCO, Guido
2011

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.
2011
hybrid logics; interval length binders; interval neighbourhood logics; tiling; undecidability;
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/2326790
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact