Since the work of Rabin [9], it has been known that any monadic second order property of the (labeled) binary tree with successor functions (and not the prefix ordering) is a monadic Δ3 property. In this paper, we show this upper bound is optimal in the sense that there is a monadic Σ2 formula, stating the existence of a path where a given predicate holds infinitely often, which is not equivalent to any monadic Σ2 formula. We even show that some monadic second order definable properties of the binary tree are not definable by any boolean combination of monadic Σ2 and Σ2 formulas. These results rely in particular on applications of Ehrenfeucht-Fraïssé like game techniques to the case of monadic Σ2 formulas.

On the structure of the monadic logic of the binary tree (MFCS 1999)

LENZI, Giacomo;
1999-01-01

Abstract

Since the work of Rabin [9], it has been known that any monadic second order property of the (labeled) binary tree with successor functions (and not the prefix ordering) is a monadic Δ3 property. In this paper, we show this upper bound is optimal in the sense that there is a monadic Σ2 formula, stating the existence of a path where a given predicate holds infinitely often, which is not equivalent to any monadic Σ2 formula. We even show that some monadic second order definable properties of the binary tree are not definable by any boolean combination of monadic Σ2 and Σ2 formulas. These results rely in particular on applications of Ehrenfeucht-Fraïssé like game techniques to the case of monadic Σ2 formulas.
1999
3-540-66408-4
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/1954329
 Attenzione

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

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