In this paper we consider the alternation hierarchy of the modal μ-calculus over finite symmetric graphs and show that in this class the hierarchy is infinite. The μ-calculus over the symmetric class does not enjoy the finite model property, hence this result is not a trivial consequence of the strictness of the hierarchy over symmetric graphs. We also find a lower bound and an upper bound for the satisfiability problem of the μ-calculus over finite symmetric graphs.

On the Modal μ-Calculus over Finite Symmetric Graphs

D'AGOSTINO, Giovanna;
2015-01-01

Abstract

In this paper we consider the alternation hierarchy of the modal μ-calculus over finite symmetric graphs and show that in this class the hierarchy is infinite. The μ-calculus over the symmetric class does not enjoy the finite model property, hence this result is not a trivial consequence of the strictness of the hierarchy over symmetric graphs. We also find a lower bound and an upper bound for the satisfiability problem of the μ-calculus over finite symmetric graphs.
File in questo prodotto:
File Dimensione Formato  
03_422-13_DAgostino-Lenzi.pdf

non disponibili

Descrizione: Articolo Principale
Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 216.46 kB
Formato Adobe PDF
216.46 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11390/1069228
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact