Robert Wille, Aaron Lye, Philipp Niemann,
"Checking Reversibility of Boolean Functions"
, in Simon Devitt, Ivan Lanese: Conference on Reversible Computation, Springer International Publishing, Switzerland, Seite(n) 322-337, 2016, ISBN: 978-3-319-40577-3
Original Titel:
Checking Reversibility of Boolean Functions
Sprache des Titels:
Englisch
Original Buchtitel:
Conference on Reversible Computation
Original Kurzfassung:
Following the reversible computation paradigm is essential in
the design of many emerging technologies such as quantum computation
or dedicated low power concepts. The design of corresponding circuits
and systems heavily relies on information about whether the function
to be realized is indeed reversible. In particular in hierarchical synthesis
approaches where a given function is decomposed into sub-functions, this
is often not obvious. In this paper, we prove that checking reversibility
of Boolean functions is indeed coNP-complete. Besides that, we propose
two complementary approaches which, despite the complexity, can tackle
this problem in an efficient fashion. An experimental evaluation shows
the feasibility of the approaches.
Forschungs-