## Fixed point characterization of weak monadic logic definable sets of trees.(English)Zbl 0794.03054

Nivat, Maurice (ed.) et al., Tree automata and languages. Amsterdam etc.: North-Holland. Stud. Comput. Sci. Artif. Intell. 10, 159-188 (1992).
Weak monadic second-order logic (WS2S) restricts the range of quantifiers to finite sets. The formulas of WS2S correspond exactly (with regard to the definability sets of trees) to the fixed-point definitions in the powerset algebra of trees. Both least and greatest fixed-point operators may occur but no essential alternation is allowed between them.
For the entire collection see [Zbl 0781.00007].
Reviewer: A.Nabebin (Moskva)

### MSC:

 03D05 Automata and formal grammars in connection with logical questions 03B15 Higher-order logic; type theory (MSC2010) 68Q45 Formal languages and automata 05C05 Trees 68Q70 Algebraic theory of languages and automata