Transformation completeness properties of SVPC transformation sets

Transformation completeness properties of SVPC transformation sets

0.00 Avg rating0 Votes
Article ID: iaor1992356
Country: Netherlands
Volume: 32
Issue: 3
Start Page Number: 263
End Page Number: 273
Publication Date: Aug 1991
Journal: Discrete Applied Mathematics
Authors: , ,
Abstract:

A set T of permutations of a finite set equ1 is said to be transformation complete if the orbits of equ2, the group generated by T, acting on equ3, the power set of equ4, are exactly the set of subsets of equ5 having the same cardinality, where the orbit of equ6 is equ7. This paper studies the transformation completeness properties of suppressed variable permutation and complementation (SVPC) transformations with act on Boolean variables with domian being equ8. An SVPC transformation with r control variables is an identity on the n-cube except on an (n-r)-subcube where the acting is like a variable permutation and complementation (VPC) transformation on n-r variables, equ9. Let equ10 be the set of all SVPC transformations on n variables with r control variables. It is shown that equ11 is transformation complete for equ12. In particular, it is shown that equ13. where equ14 and equ15 are the symmetric group and alternating group of degree equ16, respectively. equ17, i.e., the VPC transformation group on n variables, is not transformation complete, however, Thus, one control variable is necessary and sufficient to make equ18 transformation complete.

Reviews

Required fields are marked *. Your email address will not be published.