Join-irreducible Boolean functions

DOI10.1007/S11083-010-9175-ZzbMATH Open1204.06008arXiv0903.3848OpenAlexW1981167177MaRDI QIDQ603893FDOQ603893

Authors: Moncef Bouaziz, Miguel Couceiro, Maurice Pouzet 

Publication date: 8 November 2010

Published in: Order (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

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

Cited In (10)

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

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)