Descriptive complexity of modularity problems on graphs

MaRDI QIDQ3435237zbMATH OpenFDO

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

Publication date 25 April 2007

Mathematics Subject Classification ID

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

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)

• The complexity of modular graph automorphism
• scientific article; zbMATH DE number 1136076 (Why is no real title available?)
• scientific article; zbMATH DE number 7378595 (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)