Join-irreducible Boolean functions

Bouaziz, Moncef; Pouzet, Maurice; Couceiro, Miguel

Bouaziz, Moncef; Pouzet, Maurice; Couceiro, Miguel (2010), Join-irreducible Boolean functions, Order, 27, 3, p. 261-282. http://dx.doi.org/10.1007/s11083-010-9175-z

Type

Article accepté pour publication ou publié

External document link

http://arxiv.org/abs/0903.3848

Date

2010

Journal name

Order

Volume

Number

Publisher

Springer

Pages

261-282

Abstract (EN)

This paper is a contribution to the study of a quasi-order on the set Ω of Boolean functions, the simple minor quasi-order. We look at the join-irreducible members of the resulting poset . 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 are the − 2-monomorphic Steiner systems. We also describe the graphs which correspond to join-irreducible members of .

Subjects / Keywords

monomorphy; Steiner systems; designs; hypergraph; minor quasi-order; Boolean function