Generic complexity of first-order theories

MaRDI QIDQ890867zbMATH OpenFDO

Authors Alexander Rybalov

Publication date 16 November 2015

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

Full work available at URL http://semr.math.nsc.ru/v8/p168-178.pdf

zbMATH Keywords

first-order theorygeneric complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Generic undecidability of universal theories
• Generic complexity of Presburger arithmetic
• Generic Complexity of Presburger Arithmetic
• On generic complexity of the existential theories
• On generic complexity of the validity problem for Boolean formulas

Cited in

(13)

• Dynamic notions of genericity and array noncomputability
• On the generic existential theory of finite graphs
• Generic undecidability of universal theories
• The complexity of definability by open first-order formulas
• Generic Complexity of Presburger Arithmetic
• The Exact Complexity of the First-Order Logic Definability Problem
• On generic complexity of the existential theories
• Circuit complexity and the expressive power of generalized first-order formulas
• scientific article; zbMATH DE number 2222019 (Why is no real title available?)
• scientific article; zbMATH DE number 7333179 (Why is no real title available?)
• The Complexity of Decomposing Modal and First-Order Theories
• Inductive Logic Programming
• Generic complexity of Presburger arithmetic

This page was built for publication: Generic complexity of first-order theories

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