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-01-01

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.
2001
0-7695-1281-X
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1954323
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact