scientific article; zbMATH DE number 1519892

MaRDI QIDQ4509902zbMATH OpenFDO

Authors Ulrich Weigand

Publication date 19 October 2000

zbMATH Keywords

complexity classesmonadic second-order logictransitive closuredescriptive complexity

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• scientific article; zbMATH DE number 1043779
• Expressive power of monadic logics on words, trees, pictures, and graphs
• Languages that Capture Complexity Classes
• scientific article; zbMATH DE number 2087211

Cited in

(4)

• Simple proof of the completeness theorem for second-order classical and intuitionistic logic by reduction to first-order mono-sorted logic
• Uniformization and skolem functions in the class of trees
• Directed Nowhere Dense Classes of Graphs
• Computability by monadic second-order logic

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 Q4509902)