Reversible P Systems to Simulate Fredkin Circuits

• Autorzy: Leporati A. , Zandron C. , Mauri G.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

energy-based P systems; reversible Fredkin circuits

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 529--548
• Opis fizyczny: bibliogr. 37 poz., wykr.

Twórcy

autor

Leporati A.

autor

Zandron C.

autor

Mauri G.

• Dipartimento di Informatica, Sistemistica e Communicazione, Universita degli Studi di Milano-Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy,

Bibliografia

• [1] Alford, G.: Membrane Systems with Heat Control, Pre-Proceedings of the Workshop on Membrane Computing, Curtea de Arges, Romania, August 2002.
• [2] Athas, W. C., Svensson, L. J., Koller, J. G., Tzartzanis, N., Chou, E.: Low-Power Digital Systems Based on Adiabatic-Switching Principles, IEEE Transactions on VLSI Systems, 2(4), 1994, 398-407.
• [3] Bekenstein, J. D.: Energy Cost of Information Transfer, Physical Review Letters, 46(10), 1981, 623-626.
• [4] Bennett, C. H.: Logical Reversibility of Computation, IBM Journal of Research and Development, 17, November 1973, 525-532.
• [5] Bennett, C. H.: Notes on the History of Reversible Computation, IBM Journal of Research and Development, 32, 1988, 16-23.
• [6] Cattaneo, G., Leporati, A., Leporini, R.: FredkinGates for Finite-valued Reversible and Conservative Logics, Journal of Physics A: Mathematical and General, 35, November 2002, 9755-9785.
• [7] Ceterchi, R., Sburlan, D.: Simulating Boolean Circuits with P Systems, Membrane Computing, Proceedings of the InternationalWorkshop WMC 2003, (C.Martin-Vide, G.Mauri, Gh. Pǎun, G. Rozenberg, A. Salomaa, Eds.), LNCS 2933, Springer-Verlag, Berlin, 2004, 104-122.
• [8] Erk, K.: Simulating Boolean Circuits by Finite Splicing, Proceedings of the Congress on Evolutionary Computation, 2(6-9), IEEE Press, 1999, 1279-1285.
• [9] Fredkin, E., Toffoli, T.: Conservative Logic, International Journal of Theoretical Physics, 21(3-4), 1982, 219-253.
• [10] Freund, R.: Energy-Controlled P Systems, Membrane Computing, Proceedings of the International Workshop WMC-CdeA 2002, (G. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron, Eds.), LNCS 2597, Springer-Verlag, Berlin, 2003, 247-260.
• [11] Freund, R., Leporati, A., Oswald, M., Zandron, C.: Sequential P Systems with Unit Rules and Energy Assigned to Membranes, Machines, Computations, and Universality: 4th International Conference, MCU 2004, (M. Margenstern, Ed.), LNCS 3354, Springer-Verlag, Berlin, 2005, 200-210.
• [12] Frisco, P.: The Conformon-P System: a Molecular and Cell Biology-inspired Computability Model, Theoretical Computer Science, 312, 2004, 295-319.
• [13] Frisco, P., Ji, S.: Info-energy P Systems, Proceedings of DNA 8, Eighth InternationalMeeting on DNA Based Computers, Hokkaido University, Japan, June 2002.
• [14] Hall, J. S: An Electroid Switching Model for Reversible Computer Architectures, Proceedings of the Workshop on Physics and Computation, PhysComp '93, IEEE Press, 1993.
• [15] Ji, S.: The Bhopalator: An Information/Energy Dual Model of the Living Cell, Fundamenta Informaticae, 49(1-3), 2002, 147-165.
• [16] Klein, J.P., Leete, T.H., Rubin, H.: A Biomolecular Implementation of Logically Reversible Computation with Minimal Energy Dissipation, Biosystems, 52, 1999, 15-23.
• [17] Koller, J. G, Athas, W. C.: Adiabatic Switching, Low Energy Computing, and the Physics for Storing and Erasing Information, Proceedings of theWorkshop on Physics and Computation, PhysComp '92, IEEE Press, 1992.
• [18] Landauer, R.: Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, 5, 1961, 183-191.
• [19] Landauer, R.: Uncertainty Principle and Minimal Energy Dissipation in the Computer, International Journal of Theoretical Physics, 21(3-4), 1982, 283-297.
• [20] Merkle, R. C.: Reversible Electronic Logic using Switches, Nanotechnology, 4, 1993, 21-40.
• [21] Morita, K.: Construction of a Cellular Structure Memory Unit out of Fredkin's Reversible and Conservative Logic Gate, Transactions IEICE Japan, J69-D, 1986, 860-867.
• [22] Morita, K.: A Simple Construction Method of a Reversible Finite Automaton out of Fredkin Gates, and its Related Problem, Transactions IEICE Japan, E73, 1990, 978-984.
• [23] Morita, K.: Reversibility in Computation - Reversible Turing Machines and Reversible Logic Circuits, Journal of Information Processing Society of Japan, 35, 1994, 306-314.
• [24] Morita, K.: Reversible Cellular Automata, Journal of Information Processing Society of Japan, 35, 1994, 315-321.
• [25] Morita, K.: Reversible Simulation of One-dimensional IrreversibleCellular Automata, Theoretical Computer Science, 148, 1995, 157-163.
• [26] Morita, K.: Universality of a Reversible Two-Counter Machine, Theoretical Computer Science, 168, 1996, 306-314.
• [27] Morita, K., Imai, K.: Number-Conserving Reversible Cellular Automata and their Computation-Universality, Proceedings of MFCS '98 Satellite Workshop on Cellular Automata, Brno, 1998, 51-68.
• [28] Ogihara, M., Ray, A.: Simulating Boolean Circuits on a DNA Computer, Technical Report 631, 1996, available at: http://citeseer.nj.nec.com/ogihara96simulating.html
• [29] Pǎun, Gh.: Computing with Membranes, Journal of Computer and System Sciences, 1(61), 2000, 108-143. See also Turku Centre for Computer Science, TUCS Report No. 208, 1998.
• [30] Pǎun, Gh.: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002.
• [31] Pǎun, Gh., Suzuki, Y., Tanaka, H.: P Systems with Energy Accounting, International Journal Computer Math., 78(3), 2001, 343-364.
• [32] Petri, C. A.: Gründsatzliches zur Beschreibung Diskreter Prozesse, Proceedings of the 3 rd Colloquium über Automatentheorie (Hannover, 1965), Birkhäuser Verlag, Basel, 1967, 121-140. English translation: Fundamentals of the Representation of Discrete Processes, ISF Report 82.04, 1982.
• [33] The P systems Web page: http://psystems.disco.unimib.it/
• [34] Toffoli, T.: Reversible Computing, MIT/LCS Technical Report 51, February 1980.
• [35] Van de Snepscheut, J. L. A.: Reversible Computations. What Computing is all About. Springer-Verlag, Berlin, 1993.
• [36] Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach, Springer-Verlag, 1999.
• [37] Younis, S. G., Knight, T. F.: Practical Implementation of Charge Recovering Asymptotically Zero Power Cmos, Proceedings of the 1993 Symposium on Integrated Systems, MIT Press, 1993.