Reference : Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/10993/3199
Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms
English
Lehtonen, Erkko mailto [Tampere University of Technology, Finland / University of Waterloo, Canada]
Nešetřil, Jaroslav mailto [Charles University, Czech Republic]
2010
European Journal of Combinatorics
Elsevier
31
8
1981-1995
Yes (verified by ORBilu)
International
0195-6698
[en] Each clone C on a fixed base set A induces a quasi-order on the set of all operations on A by the following rule: f is a C-minor of g if f can be obtained by substituting operations from C for the variables of g. By making use of a representation of Boolean functions by hypergraphs and hypergraph homomorphisms, it is shown that a clone C on {0,1} has the property that the corresponding C-minor partial order is universal if and only if C is one of the countably many clones of clique functions or the clone of self-dual monotone functions. Furthermore, the C-minor partial orders are dense when C is a clone of clique functions.
http://hdl.handle.net/10993/3199
10.1016/j.ejc.2010.05.007

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
CliqueMinors.pdfAuthor postprint383.21 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.