On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula (Q1323356)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula |
scientific article; zbMATH DE number 567317
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula |
scientific article; zbMATH DE number 567317 |
Statements
On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula (English)
0 references
13 June 1995
0 references
The class of connective-free formulas (i.e., the predicate formulas built using only quantifiers and negation) is studied. The algorithmic problem of finding, for a given formula, all classically equivalent formulas with the minimal number of negations and universal quantifiers is solved (this form of minimization arises from some investigations of nested relational databases). The number of such minimal formulas is in general exponential. On the other hand, the associated decision, search and enumeration problems are solved in polynomial time.
0 references
classical predicate formulas
0 references
rewrite systems
0 references
polynomial complexity
0 references
decision problem
0 references
search problem
0 references
enumeration problem
0 references
connective-free formulas
0 references
minimal number of negations and universal quantifiers
0 references
nested relational databases
0 references
polynomial time
0 references
0.7653393149375916
0 references
0.7496247291564941
0 references
0.7476615309715271
0 references
0.7455828189849854
0 references
