6533b86dfe1ef96bd12c96c4
RESEARCH PRODUCT
On modal mu-calculus over finite graphs with bounded strongly connected components.
Giacomo LenziGiovanna D'agostinosubject
Strongly connected componentPure mathematicsComputer Science - Logic in Computer ScienceBounded functionlcsh:MathematicsModal μ-calculusComputer Science - Formal Languages and Automata Theorylcsh:Electronic computers. Computer sciencelcsh:QA1-939lcsh:QA75.5-76.95Mathematicsdescription
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).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2010-01-01 |