On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula

DOI10.1007/BF01210598zbMath0814.03004OpenAlexW1982131922MaRDI QIDQ1323356

Jan Van den Bussche

Publication date: 13 June 1995

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01210598

zbMATH Keywords

enumeration problempolynomial complexitypolynomial timenested relational databasesrewrite systemsdecision problemsearch problemclassical predicate formulasconnective-free formulasminimal number of negations and universal quantifiers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Thue systems as rewriting systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula