scientific article; zbMATH DE number 4051591
Let \(L_ 2\) be the monadic second order language for two successors arithmetic, and let \(L_{\omega 2}\) be the set of weak formulas of \(L_ 2\), i.e., formulas containing quantifiers only for individual and finite set variables. A formula of \(L_ 2\) represents a set of infinite binary trees whose nodes are labelled by symbols \(\ell\), r for two successor functions. A distance between any two trees is defined so that the obtained metric space of trees is compact. Let \(N_ 0\) denote the set of \(L_ 2\)-formulas representing closed sets of trees, and then define the sets \(N_ k\) as follows: \[ \phi \in N_{2k+1}\text{ iff } \phi \equiv \exists \alpha_ 1\exists \alpha_ 2...\exists \alpha_ n \psi \text{ where } \psi \in N_{2k}, \] \[ \phi \in N_{2k+2}\quad iff\quad \phi \equiv \forall \alpha_ 1\forall \alpha_ 2...\forall \alpha_ n \psi \text{ where } \psi \in N_{2k+1}. \] Here \(\alpha_ 1,\alpha_ 2,...,\alpha_ n\) are finite set variables. In the paper it is proved that the sets \(N_ k\) form an infinite hierarchy, more precisely, \(N_ i\subsetneqq N_{i+1}\) for \(i=0,1,2,... \). Furthermore, a characterization of representable closed sets as well as a characterization of representable open sets of trees is given in automata terms.
- Hierarchies of weak automata and weak monadic formulas
- Hierarchies of Subsystems of Weak Arithmetic
- Some new results in monadic second-order arithmetic
- Hierarchies of monadic generalized quantifiers
- scientific article; zbMATH DE number 2113976
- On Monadic Second-Order Theories of Multidominance Structures
- Monadic second-order logic and linear orderings of finite structures
- Hierarchies in Fragments of Monadic Strict NP
- Subclasses of Presburger arithmetic and the weak EXP hierarchy
- Monadic second-order logic on finite sequences
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787992)