On the Complexity of the First-order Random Theory

DOI10.1093/LOGCOM/13.2.261MaRDI QIDQ4461932zbMATH OpenOpenAlexFDO

Authors Wafik Boulos Lotfallah

Publication date 18 May 2004

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/13.2.261

zbMATH Keywords

0-1 lawcomplexity of logical theorieslogical theoryPSPACE-completeness

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• 0-1 laws and decision problems for fragments of second-order logic
• Almost everywhere elimination of probability quantifiers
• How complex are random graphs in first order logic?
• On random models of finite power and monadic logic

Cited in

(5)

• On the complexity of finite random functions
• Non-definability results for randomised first-order logic
• Complexity of the first-order theory of almost all finite structures
• Almost everywhere elimination of probability quantifiers
• Some notes on Rissanen's stochastic complexity

This page was built for publication: On the Complexity of the First-order Random Theory

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