Solving SAT and STCON by Membrane Computing Techniques

Speaker: Zsolt Gazdag, Ph.D.
Eötvös Loránd University, Budapest (Hungary)


Title: Solving SAT and STCON by Membrane Computing Techniques.

Abstract: In this talk we will consider solutions of the well known SAT and STCON problems by P systems, a class of biologically inspired computational models. Concerning the SAT problem, we will focus on the description of a family of P system that is capable to solve SAT in linear time in the number of propositional variables. In case of the STCON problem, we will describe some solutions of this problem by various classes of P systems. We will also discuss the computational power of P systems with active membranes that do not employ neither dissolution rules nor polarizations.


  • Date: Thursday, 05-12-2013
  • Time: 10:00 - 11:30.
  • Place: Seminar room of IMUS (First floor, Edificio Celestino Mutis)
  • Language: English

Organized by:

Other information: Link at IMUS