There is a problem with corollaries 6.2 and 7.2. Their proofs rely on the wrong assumption that the parity automata defined here and the standard parity alternating automata coincide level by level. So, the proofs of corollaries 6.2 and 7.2 are wrong and we do not know whether the statements are true. The summary of the paper has to be changed accordingly as follows. Summary: For every positive integer k we consider the class SCCk of all finite graphs whose strongly connected components have size at most k. We show that for every k, the Modal mu-Calculus fixpoint hierarchy on SCCk collapses to the level Delta_2; moreover, we introduce a kind of automata analogous to Janin-Walukiewicz disjunctive formulas, and we show that the mu-calculus in SCC1 does not collapse to weak automata (as they are defined here).

On modal mu-calculus over finite graphs with bounded strongly connected components.

Lenzi, G.;
2010-01-01

Abstract

There is a problem with corollaries 6.2 and 7.2. Their proofs rely on the wrong assumption that the parity automata defined here and the standard parity alternating automata coincide level by level. So, the proofs of corollaries 6.2 and 7.2 are wrong and we do not know whether the statements are true. The summary of the paper has to be changed accordingly as follows. Summary: For every positive integer k we consider the class SCCk of all finite graphs whose strongly connected components have size at most k. We show that for every k, the Modal mu-Calculus fixpoint hierarchy on SCCk collapses to the level Delta_2; moreover, we introduce a kind of automata analogous to Janin-Walukiewicz disjunctive formulas, and we show that the mu-calculus in SCC1 does not collapse to weak automata (as they are defined here).
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/11386/4704710
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact