Join-irreducible Boolean functions

DOI10.1007/S11083-010-9175-ZMaRDI QIDQ603893zbMATH OpenOpenAlexFDO

Authors Moncef Bouaziz, Miguel Couceiro, Maurice Pouzet

Publication date 8 November 2010

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.3848

zbMATH Keywords

Boolean functionhypergraphSteiner systemsdesignsminor quasi-ordermonomorphy

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Hypergraphs (05C65) Combinatorics of partially ordered sets (06A07) Boolean functions (06E30)

Abstract: This paper is a contribution to the study of a quasi-order on the set $Omega$ of Boolean functions, the emph{simple minor} quasi-order. We look at the join-irreducible members of the resulting poset $ildeOmega$. Using a two-way correspondence between Boolean functions and hypergraphs, join-irreducibility translates into a combinatorial property of hypergraphs. We observe that among Steiner systems, those which yield join-irreducible members of $ildeOmega$ are the -2-monomorphic Steiner systems. We also describe the graphs which correspond to join-irreducible members of $ildeOmega$.

Recommendations

• Conjunctively polynomial-like Boolean functions
• On irreduceability of Boolean functions with respect to commutative associative operation
• Boolean operations, joins, and the extended low hierarchy
• On connected Boolean functions
• A decomposition of Boolean functions
• Boolean reducibility
• Decomposition of Boolean functions
• scientific article; zbMATH DE number 3201638
• Disjunctive and conjunctive normal forms of pseudo-Boolean functions

Cites work

• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• scientific article; zbMATH DE number 1775542 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3216991 (Why is no real title available?)
• scientific article; zbMATH DE number 5205533 (Why is no real title available?)
• Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
• Equational characterizations of Boolean function classes
• Finite linear spaces with flag-transitive groups
• Galois theory for minors of finite functions
• Generalizations of Świerczkowski's lemma and the arity gap of finite functions
• Graph theory
• Join-irreducible Boolean functions
• On a quasi-ordering on Boolean functions
• On closed sets of relational constraints and classes of functions closed under variable substitutions
• On generalized constraints and certificates
• On the effect of variable identification on the essential arity of functions on finite sets
• Point determination in graphs
• Post classes characterized by functional terms
• Steiner triple systems with a doubly transitive automorphism group
• Steiner triple systems with block-transitive automorphism groups
• Steiner triple systems with doubly transitive automorphism groups: A corollary to the classification theorem for finite simple groups
• Theory of relations. Transl. from the French by P. Clote. With an appendix by Norbert Sauer.

Cited in

(10)

• The minor order of homomorphisms via natural dualities
• Algebras, Graphs and Ordered Sets – ALGOS 2020 & the Mathematical Contributions of Maurice Pouzet
• Parametrized arity gap
• An enumeration of distinct and non-isomorphic functional quasi-order relations
• Additive decomposability of functions over abelian groups
• Majors of functions
• Join-irreducible Boolean functions
• Content and singletons bring unique identification minors
• RECONSTRUCTING MULTISETS OVER COMMUTATIVE GROUPOIDS AND AFFINE FUNCTIONS OVER NONASSOCIATIVE SEMIRINGS
• On a quasi-ordering on Boolean functions

This page was built for publication: Join-irreducible Boolean functions

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