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.
