Monotone versus positive

DOI10.1145/31846.31852zbMath0637.94022OpenAlexW2082035816MaRDI QIDQ3778681

Miklós Ajtai, Yuri Gurevich

Publication date: 1987

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/31846.31852

zbMATH Keywords

finite structuresfirst-order formulaleast fixed point operatormonotone Boolean circuitspositive Boolean circuits

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07)

Related Items (19)

A polynomial excluded-minor approximation of treedepth ⋮ On learning monotone DNF under product distributions ⋮ Fixed-point extensions of first-order logic ⋮ Generalized quantifiers and pebble games on finite structures ⋮ Inductive definitions over finite structures ⋮ Relativised homomorphism preservation at the finite level ⋮ Positive First-order Logic on Words and Graphs ⋮ Replacement in logic ⋮ Finite-model theory -- A personal perspective ⋮ First order properties on nowhere dense structures ⋮ Homomorphism preservation on quasi-wide classes ⋮ A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries ⋮ Negation in rule-based database languages: A survey ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ Positive versions of polynomial time ⋮ Unnamed Item ⋮ Proof complexity of monotone branching programs ⋮ Context-sensitive transitive closure operators

This page was built for publication: Monotone versus positive