Closed monadic Sigma (1), as proposed in [AFS98], is the existential monadic second order logic where alternation between existential monadic second order quantifiers and first order quantifiers is allowed. Despite some effort very little is known about the expressive power of this logic on finite structures. We construct a tree automaton which exactly characterizes closed monadic Sigma (1) on the Rabin tree and give a full analysis of the expressive power of closed monadic Sigma (1) in this context. In particular, we prove that the hierarchy inside closed monadic Sigma (1), defined by the number of alternations between blocks of first order quantifiers and blocks of existential monadic second order quantifiers collapses, on the infinite tree, to the level 2.
The hierarchy inside closed monadic $Sigma_1$ collapses on the infinite binary tree
LENZI, Giacomo;
2001
Abstract
Closed monadic Sigma (1), as proposed in [AFS98], is the existential monadic second order logic where alternation between existential monadic second order quantifiers and first order quantifiers is allowed. Despite some effort very little is known about the expressive power of this logic on finite structures. We construct a tree automaton which exactly characterizes closed monadic Sigma (1) on the Rabin tree and give a full analysis of the expressive power of closed monadic Sigma (1) in this context. In particular, we prove that the hierarchy inside closed monadic Sigma (1), defined by the number of alternations between blocks of first order quantifiers and blocks of existential monadic second order quantifiers collapses, on the infinite tree, to the level 2.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.