Title: A Fine Alternation Hierarchy of the Modal Mu-calculus

Speaker: Wenjuan Li (Beijing Institute of Mathematical Sciences and Applications)

Time: Apr. 28th (Tuesday), 15:10 - 18:00

Location: Room 314, Teaching Building No.2 (北京大学第二教学楼314)

Abstract:

The modal mu-calculus extends propositional modal logic with least and greatest fixed-point operators, and is closely connected to tree automata and parity games. Its standard alternation hierarchy classifies formulas by the number of alternations between least and greatest fixpoints. We introduce a fine constructive framework: the weak alternation hierarchy and its generalizations, based on capture-free simultaneous substitutions. To establish the semantic strictness of these hierarchies, we reduce the evaluation games to a specific class of parity games whose winning regions are witnessed by certain formulas within our hierarchy. By iterating this construction, we conjecture that the syntactic hierarchy of the modal mu-calculus attains height omega to the power of omega. We further analyze the classical collapsing results for the alternation hierarchy over restricted transition systems through the lens of our weak alternation hierarchy.