Finite Convergence of the Modal Mu-Calculus on Almost-Periodic Words
For researchers in logic and automata theory, it provides a complete characterization of finite convergence on infinite words, resolving a known open question.
The paper proves that all almost-periodic words have finite convergence for the modal mu-calculus, characterizing finite convergence on infinite words and re-proving a decidability result by Semenov.
A formula of the modal mu-calculus enjoys finite convergence on a structure if there is some finite unfolding of the formula that defines the same set. A structure enjoys finite convergence if all formulas of the mu-calculus enjoy finite convergence on said structure. It is known that there are words that are not ultimately periodic, but have finite convergence. An almost-periodic word w is one in which each finite word v either appears only finitely often, or within each factor of some length that only depends only on w and v. It is immediate that words that have finite convergence must be almost periodic. In this paper we show the converse, namely that all almost-periodic words have finite convergence. This characterizes finite convergence on infinite words, and also re-proves a decidability result due to Semenov ('84).