Descriptive complexity of modularity problems on graphs

MaRDI QIDQ3435237zbMATHFDO

Authors Haroldo G. Benatti, Ruy J. G. B. de Queiroz

Publication date 25 April 2007

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Other infinitary logic (03C75) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 1163986
• Infinitary logic and inductive definability over finite structures
• Infinitary logic for computer science
• Existential second-order logic over graphs: a complete complexity-theoretic classification
• Infinitary logics and 0-1 laws

Cited in

(3)

• scientific article; zbMATH DE number 7378595 (Why is no real title available?)
• The complexity of modular graph automorphism
• scientific article; zbMATH DE number 1136076 (Why is no real title available?)

This page was built for publication: Descriptive complexity of modularity problems on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3435237)