References of "Lehtonen, Erkko 40020644"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailAn infinite descending chain of Boolean subfunctions consisting of threshold functions
Lehtonen, Erkko UL

in Proceedings of the Vienna Conference 2005 (AAA70) (2006)

For a class C of Boolean functions, a Boolean function f is a C-subfunction of a Boolean function g, if f=g(h1,...,hn), where all the inner functions hi are members of C. Two functions are C-equivalent ... [more ▼]

For a class C of Boolean functions, a Boolean function f is a C-subfunction of a Boolean function g, if f=g(h1,...,hn), where all the inner functions hi are members of C. Two functions are C-equivalent, if they are C-subfunctions of each other. The C-subfunction relation is a preorder on the set of all functions if and only if C is a clone. An infinite descending chain of U∞-subfunctions is constructed from certain threshold functions (U∞ denotes the clone of clique functions). [less ▲]

Detailed reference viewed: 30 (1 UL)
Full Text
Peer Reviewed
See detailDescending chains and antichains of the unary, linear, and monotone subfunction relations
Lehtonen, Erkko UL

in Order : A Journal on the Theory of Ordered Sets and its Applications (2006), 23(2-3), 129-142

The C-subfunction relations on the set of operations on a finite base set A defined by function classes C are examined. For certain clones C on A, it is determined whether the partial orders induced by ... [more ▼]

The C-subfunction relations on the set of operations on a finite base set A defined by function classes C are examined. For certain clones C on A, it is determined whether the partial orders induced by the respective C-subfunction relations have infinite descending chains or infinite antichains. More specifically, we investigate the subfunction relations defined by the clone of all functions on A, the clones of essentially at most unary operations, the clones of linear functions on a finite field, and the clones of monotone functions with respect to the various partial orders on A. [less ▲]

Detailed reference viewed: 86 (3 UL)
Full Text
Peer Reviewed
See detailOn the complexity of representing sets of vertices in the n-cube
Couceiro, Miguel UL; Foldes, Stephan; Lehtonen, Erkko UL

in Tsitouras, C.; Simos, T. E.; Psihoyios, G. (Eds.) ICNAAM 2005 (2005)

Representations of an arbitrary set of vertices of an n-dimensional cube in terms of convex sets are compared with respect to their complexity. The notion of complexity used in the representations is ... [more ▼]

Representations of an arbitrary set of vertices of an n-dimensional cube in terms of convex sets are compared with respect to their complexity. The notion of complexity used in the representations is based on the union, symmetric difference and ternary median operations. Convexity of a set of vertices refers to Hamming distance or, equivalently, to the intersection of cubes with supporting hyperplanes. [less ▲]

Detailed reference viewed: 31 (1 UL)
Full Text
Peer Reviewed
See detailOn compositions of clones of Boolean functions
Couceiro, Miguel UL; Foldes, Stephan; Lehtonen, Erkko UL

in Simos, T.; Maroulis, G. (Eds.) International Conference of Computational Methods in Sciences and Engineering 2004 (ICCMSE 2004) (2004)

We present some compositions of clones of Boolean functions that imply factorizations of ?, the clone of all Boolean functions, into minimal clones. These can be interpreted as representation theorems ... [more ▼]

We present some compositions of clones of Boolean functions that imply factorizations of ?, the clone of all Boolean functions, into minimal clones. These can be interpreted as representation theorems, providing representations of Boolean functions analogous to the disjunctive normal form, the conjunctive normal form, and the Zhegalkin polynomial representations. [less ▲]

Detailed reference viewed: 89 (0 UL)