scientific article; zbMATH DE number 1519892

zbMATH Open0954.03039MaRDI QIDQ4509902FDOQ4509902

Authors: Ulrich Weigand 

Publication date: 19 October 2000

Title of this publication is not available (Why is that?)

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

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)

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)