Antonio E. Porreca

Antonio E. Porreca (porreca@disco.unimib.it)
Dipartimento di Informatica, Sistemistica e Comunicazione
Università degli Studi di Milano-Bicocca
Room 1047, Viale Sarca 336/14, 20126 Milano, Italy

I am a postdoctoral fellow at Dipartimento di Informatica, Sistemistica e Comunicazione (DISCo) of Università degli Studi di Milano-Bicocca, Italy.

My current research interest is the computational complexity theory of membrane systems (usually called P systems), computing devices inspired by the internal structure and functioning of biological cells, introduced by Gheorghe Păun about a decade ago.

I think P systems, especially their variant with so-called active membranes, are interesting from a complexity-theoretic standpoint for their ability to solve hard problems, NP and sometimes even PSPACE-complete ones, in polynomial time by using membrane division (a process inspired by mitosis). The price of this time-efficiency is an exponential workspace, and formalising and investigating this trade-off is an important part of my Ph.D. work, which is carried out under the supervision of Prof. Claudio Zandron and in collaboration with Dr. Alberto Leporati and Prof. Giancarlo Mauri of the “Milano membrane computing team”.

I am also interested in the theory of computation in general, mathematical logic and functional programming (although at present I am not planning to do research in these fields).

From January to July 2011 I was a visiting Ph.D. student at Research Group on Natural Computing, Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla, Spain.

Papers

This is a list of my publications and other writings. Click on the title to go to the publisher’s website for the paper (if any), or on the PDF link to get a preprint.

Journal papers

• A.E. Porreca, G. Mauri, C. Zandron, Complexity classes
  for membrane systems, RAIRO Theoretical Informatics and Applications 40(2), 141–162, 2006 [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, Introducing a space complexity measure for P systems, International Journal of Computers, Communications & Control 4(3), 301–310, 2009 (invited paper) [PDF]
• A.E. Porreca, G. Mauri, C. Zandron, Non-confluence in divisionless P systems with active membranes, Theoretical Computer Science 411(6), 878–887, 2010 [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, P systems with active membranes: Trading time for space, Natural Computing 10(1), 167–182, 2011 [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, Complete problems for a variant of P systems with active membranes, Romanian Journal of Information Science and Technology 13(2), 197–207, 2010 (invited paper) [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, P systems with active membranes working in polynomial space, International Journal of Foundations of Computer Science 22(1), 65–73, 2011 [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, Elementary active membranes have the power of counting, International Journal of Natural Computing Research 2(3), 35–48, 2011 (invited paper) [PDF]

Conference papers

• A. Valsecchi, A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, An efficient simulation of polynomial-space Turing machines by P systems with active membranes, in G. Păun, M.J. Pérez-Jiménez, A. Riscos-Núñez, G. Rozenberg, A. Salomaa (eds.), Membrane Computing, 10th International Workshop, WMC 2009, Lecture Notes in Computer Science 5979, 461–478, 2010 (Best Paper Award at WMC10) [PDF]
• G. Mauri, A. Leporati, A.E. Porreca, C. Zandron, Computational complexity aspects in membrane computing, in F. Ferreira, B. Löwe, E. Mayordomo and L. Mendes Gomes (eds.), Programs, Proofs, Processes, 6th Conference on Computability in Europe, CiE 2010, Lecture Notes in Computer Science 6158, 317–320, 2010 [PDF]
• A.E. Porreca, A. Leporati, C. Zandron, On a powerful class of non-universal P systems with active membranes, in Y. Gao, H. Lu, S. Seki, S. Yu (eds.), Developments in Language Theory, 14th International Conference, DLT 2010, Lecture Notes in Computer Science 6224, 364–375, 2010 [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, P systems with elementary active membranes: Beyond NP and coNP, in M. Gheorghe, T. Hinze, G. Păun, G. Rozenberg, A. Salomaa (eds.), Membrane Computing, 11th International Conference, CMC 2010, Lecture Notes in Computer Science 6501, 338–347, 2011 [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, P systems simulating oracle computations, in M. Gheorghe, G. Păun, G. Rozenberg, A. Salomaa, S. Verlan (eds.), Membrane Computing, 12th International Conference, CMC 2011, Lecture Notes in Computer Science 7184, 346–358, 2012 (Best Paper Award at CMC 2011) [PDF]

Technical reports

• A.E. Porreca, N. Murphy, First steps towards linking membrane depth and the Polynomial Hierarchy, in M.A. Martínez-del-Amor, G. Păun, I. Pérez-Hurtado, A. Riscos-Núñez (eds.), Eight Brainstorming Week on Membrane Computing, RGNC Report 1/2010, 255–266, 2010 [PDF]
• A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, Elementary active membranes have the power of counting, in M.A. Martínez-del-Amor, G. Păun, I. Pérez-Hurtado, F.J. Romero-Campero, L. Valencia-Cabrera (eds.), Ninth Brainstorming Week on Membrane Computing, RGNC Report 1/2011, 329–342, 2011 [PDF]
• A. Alhazov, A. Leporati, G. Mauri, A.E. Porreca, C. Zandron, The computational power of exponential-space P systems with active membranes, in M.A. Martínez-del-Amor, G. Păun, I. Pérez-Hurtado, F.J. Romero-Campero (eds.), Tenth Brainstoming Week on Membrane Computing, RGNC Report 1/2012, Volume I, 35–60, 2012 [PDF]
• A.E. Porreca, N. Murphy, M.J. Pérez-Jiménez, An optimal frontier of the efficiency of tissue P systems with cell division, in M.A. Martínez-del-Amor, G. Păun, I. Pérez-Hurtado, F.J. Romero-Campero (eds.), Tenth Brainstoming Week on Membrane Computing, RGNC Report 1/2012, Volume II, 141–166, 2012 [PDF]

Unpublished papers

• G. Mauri, A. Leporati, A.E. Porreca, C. Zandron, Recent complexity-theoretic results on P systems with active membranes, submitted

Other writings

• Review of the book Algorithmic Adventures: From Knowledge to Magic by J. Hromkovič [PDF]