Monotone versus positive

DOI10.1145/31846.31852MaRDI QIDQ3778681zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On Testing Monotone Tendencies
• Monotone Series
• Monotone normality
• Monotone normality
• Monotone persuasion
• Beyond complete positivity
• Semi-positivity in positive characteristics
• scientific article; zbMATH DE number 3843617
• Monotonically positive matrices
• scientific article; zbMATH DE number 2088330

Cited in

(25)

• On the minimum number of negations leading to super-polynomial savings
• Fixed-point extensions of first-order logic
• Positive versions of polynomial time
• Context-sensitive transitive closure operators
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Relativised homomorphism preservation at the finite level
• On learning monotone DNF under product distributions
• Generalized quantifiers and pebble games on finite structures
• Replacement in logic
• Proof complexity of monotone branching programs
• A polynomial excluded-minor approximation of treedepth
• A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries
• Inductive definitions over finite structures
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• First order properties on nowhere dense structures
• Positive First-order Logic on Words and Graphs
• Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
• Preservation theorems through the Lens of topology
• Finite-model theory -- A personal perspective
• The umbilical cord of finite model theory
• Proof complexity of positive branching programs
• Polynomial threshold functions of bounded tree-width: some explainability and complexity aspects
• Homomorphism preservation theorems for many-valued structures
• Negation in rule-based database languages: A survey
• Homomorphism preservation on quasi-wide classes

This page was built for publication: Monotone versus positive

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