The evolution of Description Logics (DLs) and Propositional Dynamic Logics produced a hierarchy of decidable logics with multiple maximal elements. It would be desirable to combine different maximal logics into one super-logic, but then inference may turn out to be undecidable. Then it is important to characterize the decidability threshold for these logics. In this perspective, an interesting open question pointed out by Sattler and Vardi is whether inference in a hybrid mu-calculus with restricted forms of graded modalities is decidable, and which complexity class it belongs to. In this paper we improve a previous result and prove that this calculus and the corresponding DL mu-ALCIO_fa are undecidable. We show also that nested fixpoints are not necessary for undecidability.

On the undecidability of logics with nominals, recursion and counting / Bonatti, PIERO ANDREA; Peron, Adriano. - In: ARTIFICIAL INTELLIGENCE. - ISSN 0004-3702. - STAMPA. - 158:(2004), pp. 75-96. [10.1016/j.artint.2004.04.012]

On the undecidability of logics with nominals, recursion and counting

BONATTI, PIERO ANDREA;PERON, ADRIANO
2004

Abstract

The evolution of Description Logics (DLs) and Propositional Dynamic Logics produced a hierarchy of decidable logics with multiple maximal elements. It would be desirable to combine different maximal logics into one super-logic, but then inference may turn out to be undecidable. Then it is important to characterize the decidability threshold for these logics. In this perspective, an interesting open question pointed out by Sattler and Vardi is whether inference in a hybrid mu-calculus with restricted forms of graded modalities is decidable, and which complexity class it belongs to. In this paper we improve a previous result and prove that this calculus and the corresponding DL mu-ALCIO_fa are undecidable. We show also that nested fixpoints are not necessary for undecidability.
2004
On the undecidability of logics with nominals, recursion and counting / Bonatti, PIERO ANDREA; Peron, Adriano. - In: ARTIFICIAL INTELLIGENCE. - ISSN 0004-3702. - STAMPA. - 158:(2004), pp. 75-96. [10.1016/j.artint.2004.04.012]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS 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/11588/203168
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact