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)


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