Complexity of the first-order theory of almost all finite structures

1983/05/01 by Étienne Grandjean, Etienne Grandjean · 5 citations
Computer Science · Mathematics · #Business #Complexity and Algorithms in Graphs #Computer science #Finite Group Theory Research #Mathematics #Order (exchange) #Theoretical computer science #semigroups and automata theory

paper · doi:10.1016/s0019-9958(83)80043-6

crossref issued 1983/05/01 · crossref published 1983/05/01 · crossref published-print 1983/05/01 · openalex publication_date 1983/05/01 · crossref created 2005/05/06 · crossref deposited 2019/01/26 · openalex created_date 2025/10/10 · crossref indexed 2025/11/01 · openalex updated_date 2026/08/05

Citations

• The complexity of logical theories
• Alternation
• Concerning measures in first order calculi
• Probabilities on finite models
• Probabilities on finite models

Cited by

• Probabilities of Sentences about Very Sparse Random Graphs
• Finite-model theory - a personal perspective
• Convergence Laws for Extensions of First-Order Logic with Averaging
• Finite model theory [wikipedia]
• Logic of graphs [wikipedia]
• Rado graph [wikipedia]