We consider the μ-calculus over graphs where the accessibility relation is an equivalence (S5-graphs). We show that the vectorial μ-calculus model checking problem over arbitrary graphs reduces to the vectorial, existential μ-calculus model checking problem over S5 graphs. Moreover, we give a proof that satisfiability of μ-calculus in S5 is NP-complete, and by using S5 graphs we give a new proof that the satisfiability problem of the existential μ-calculus is also NP-complete. Finally we prove that on multimodal S5, in contrast with the monomodal case, the fixpoint hierarchy of the μ-calculus is infinite and the finite model property fails.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We introduce and prove the basic properties of encodings that generalize to non-wellfounded hereditarily finite sets the bijection defined by Ackermann in 1937 between hereditarily finite sets and natural numbers.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.