Generic complexity of first-order theories

zbMATH Open1329.03076MaRDI QIDQ890867FDOQ890867

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

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

zbMATH Keywords

first-order theorygeneric complexity

Mathematics Subject Classification ID

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

Cited In (13)

• The Exact Complexity of the First-Order Logic Definability Problem
• Title not available (Why is that?)
• Circuit complexity and the expressive power of generalized first-order formulas
• Generic complexity of Presburger arithmetic
• Generic Complexity of Presburger Arithmetic
• Title not available (Why is that?)
• On the generic existential theory of finite graphs
• Inductive Logic Programming
• The Complexity of Decomposing Modal and First-Order Theories
• The complexity of definability by open first-order formulas
• On generic complexity of the existential theories
• Dynamic notions of genericity and array noncomputability
• Generic undecidability of universal theories

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)