Reversible P Systems to Simulate Fredkin Circuits

Issue title: SPECIAL ISSUE MCU2004

Article type: Research Article

Authors: Leporati, Alberto | Zandron, Claudio | Mauri, Giancarlo

Affiliations: Dipartimento di Informatica, Sistemistica e Comunicazione Università degli Studi di Milano – Bicocca Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy. E-mail: {leporati,zandron,mauri}@disco.unimib.it

Abstract: We introduce energy-based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. Basing upon the seminal paper of Fredkin and Toffoli on conservative logic, we first show how energy-based P systems can be used to simulate the Fredkin gate, a reversible and conservative three-input/three-output boolean gate which is functionally complete for boolean logic. Then, we show how any reversible Fredkin circuit can be simulated by energy-based P systems whose number of membranes is independent of the number of gates occurring in the simulated circuit. The simulating P systems turn out to be themselves reversible and conservative.

Keywords: Energy-based P systems, reversible Fredkin circuits

Journal: Fundamenta Informaticae, vol. 74, no. 4, pp. 529-548, 2006