Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875307 | Science of Computer Programming | 2018 | 16 Pages |
Abstract
We say that a reversible boolean function on n bits has alternation depth d if it can be written as the sequential composition of d reversible boolean functions, each of which acts only on the top nâ1 bits or on the bottom nâ1 bits. Moreover, if the functions on nâ1 bits are even, we speak of even alternation depth. We show that every even reversible boolean function of n⩾4 bits has alternation depth at most 9 and even alternation depth at most 13.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Peter Selinger,