COMPLEXITY OF UNIVERSAL CIRCUMSCRIPTION

DOI10.1142/S0129054193000158MaRDI QIDQ4286111zbMATH OpenOpenAlexFDO

Authors Alexej P. Lisitsa

Publication date 27 April 1994

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054193000158

zbMATH Keywords

model checkingcircumscriptionfinite modelsCoNP-completeness

Mathematics Subject Classification ID

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

Recommendations

• Some computational aspects of circumscription
• The complexity of model checking for circumscriptive formulae
• scientific article; zbMATH DE number 1884382
• On the computability of circumscription
• Decidability and definability with circumscription

Cited in

(5)

• The complexity of model checking for circumscriptive formulae
• On complexity of the anti-unification problem
• Universal first-order logic is superfluous for NL, P, NP and coNP
• Complexity of hyperconcepts
• Some computational aspects of circumscription

This page was built for publication: COMPLEXITY OF UNIVERSAL CIRCUMSCRIPTION

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