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
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).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
