Arnold, André; Niwiński, Damian 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) Cited in 15 Documents 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 Keywords:tree automaton; fixed point; weak monadic second order logic; powerset algebra of trees PDFBibTeX XMLCite \textit{A. Arnold} and \textit{D. Niwiński}, Stud. Comput. Sci. Artif. Intell. 10, 159--188 (1992; Zbl 0794.03054)