On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components

Details On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components

2010-06-08

arxiv.org/abs/1006.1406v1

EPTCS 25, 2010, pp. 55-71

Computer Science

Logic in Computer Science

Scientific paper

10.4204/EPTCS.25.9

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 Delta2, but not to Comp(Sigma1,Pi1) (compositions of formulas of level Sigma1 and Pi1). This contrasts with the class of all graphs, where Delta2=Comp(Sigma1,Pi1).

Affiliated with

Also associated with

No associations

Rating

On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Modal μ-Calculus over Finite Graphs with Bounded Strongly Connected Components will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-29303