On m-junctive predicates on a finite set

DOI10.1134/S199047891903013XMaRDI QIDQ4973259zbMATH OpenOpenAlexWikidataFDO

Authors Svetlana N. Selezneva

Publication date 2 December 2019

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s199047891903013x

zbMATH Keywords

conjunctive normal formgeneralized satisfiability problembijunctive predicatenear-unanimity function\(m\)-junctive predicatefunction on a finite setpredicate on a finite set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Descriptive complexity and finite models (68Q19)

Recommendations

• On bijunctive predicates over a finite set
• On weak positive predicates over a finite set
• Universal algebras generated by sets of satisfying vectors of bijunctive and \(r\)-junctive Boolean functions
• scientific article; zbMATH DE number 4041859
• On properties of functions representable in the form of a 2-CNF

Cites work

• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• An optimal k-consistency algorithm
• Classifying the Complexity of Constraints Using Finite Algebras
• Closure properties of constraints
• Constraints, consistency and closure
• From local to global consistency
• Function Algebras on Finite Sets
• On bijunctive predicates over a finite set
• On weak positive predicates over a finite set
• The complexity of satisfiability problems
• The property of being polynomial for Mal’tsev constraint satisfaction problems
• Tractable constraints on ordered domains

Cited in

(5)

• On properties of multiaffine predicates on a finite set
• scientific article; zbMATH DE number 7297896 (Why is no real title available?)
• Universal algebras generated by sets of satisfying vectors of bijunctive and \(r\)-junctive Boolean functions
• On weak positive predicates over a finite set
• On bijunctive predicates over a finite set

This page was built for publication: On \(m\)-junctive predicates on a finite set

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