scientific article; zbMATH DE number 4051591

MaRDI QIDQ3787992zbMATH OpenFDO

Authors A. Włodzimierz Mostowski

Publication date 1987

zbMATH Keywords

metric space of treesbounded formula suffixmonadic second order language for two successors arithmeticrepresentable closed setsrepresentable open setsThomas hierarchy

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Second- and higher-order arithmetic and fragments (03F35)

Recommendations

• 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
• scientific article; zbMATH DE number 2079025
• Hierarchies in Fragments of Monadic Strict NP
• Subclasses of Presburger arithmetic and the weak EXP hierarchy
• Monadic second-order logic on finite sequences

Cited in

(4)

• scientific article; zbMATH DE number 1841846 (Why is no real title available?)
• The Borel hierarchy is infinite in the class of regular sets of trees
• Hierarchies of weak automata and weak monadic formulas
• Monadic second order definable relations on the binary tree

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)