On the generic existential theory of finite graphs

DOI10.33048/SEMI.2020.17.115MaRDI QIDQ2212708zbMATH OpenOpenAlexFDO

Authors Alexander Rybalov

Publication date 24 November 2020

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL https://doi.org/10.33048/semi.2020.17.115

zbMATH Keywords

generic theorygraphs

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Applications of model theory (03C98) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On generic complexity of the existential theories
• On complexity of the existential and universal theories of finite fields
• Generic complexity of first-order theories
• Decidability of the restricted theories of a class of partial orders
• Undecidable statements and random graphs

Cites work

• Algebraic geometry over algebraic structures. III: Equationally Noetherian property and compactness
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)

Cited in

(6)

• Annotation theories over finite graphs
• Properties of Almost All Graphs and Generalized Quantifiers
• On complexity of the existential and universal theories of finite fields
• On generic complexity of the existential theories
• Existential and positive theories of equations in graph products
• Structure of the set of generating graphs in the theory of pseudocriteria

This page was built for publication: On the generic existential theory of finite graphs

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