2
$\begingroup$

If we expand modal logic with least and greatest fix point operators $\mu$ and $\nu$, respectively, we obtain the logic $L_\mu$.

An alternating automaton on infinite trees has a state space that is divided between two players, $\exists$ and $\forall$. Transitions of this automaton assign both a new state and a movement directive in the graph. Whether such an automaton accepts a tree is based on a two-player parity game. A player has to first choose a transition and depending on whether that transition involves a forward move or not, the game either remains in the same vertex or the player has to additionally choose one of the successors of the current vertex. If player $\exists$ wins this game with a positional strategy $s$ then the tree is accepted by the automaton.

It is now possible to translate such $L_\mu$ formulae to alternating automata on infinite trees by introducing a state for each subformula and choosing the transition function in a way that reflects the current formula. This would mean if the current formula is a disjunction of two subformulae, player $\exists$ could choose between the two states representing the subformulae.

The translation for fixed point operators is done by essentially starting a recursion on the subformula, meaning $\mu X \varphi$ is expanded to the state representing $\varphi$.

My question is now: why is it not allowed that such a least fix point operator is expanded infinitely often, while it would be acceptable for a greatest fix point operator?

$\endgroup$
1
  • 2
    $\begingroup$ Hi, Max. You might be better off posting this on cstheory.stackexchange.com, Most of the experts in modal logic I know live in computer science departments, not maths ones, although of course there are exceptions! $\endgroup$ Commented Jan 6, 2018 at 12:20

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.