PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Powiadomienia systemowe
  • Sesja wygasła!
Tytuł artykułu

Membrane Systems with Coupled Transport: Universality and Normal Forms

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
This paper continues research on membrane systems which function by communication only, meaning that there are no evolving rules for molecules. The whole computation process relies on passage of molecules through membranes - this provides communication between regions of the membrane system. Next to transport of single molecules through membranes (uniport) we also study a coupled transport of molecules, with two molecules passing either in the same direction (symport) or in opposite directions (antiport). We study the computational power of such membrane systems and prove that using only symport one gets Turing universality. Moreover, we prove that five membranes suffice to get Turing universality, and the number of membranes can be decreased to three if forbidding context conditions for transport are used.
Wydawca
Rocznik
Strony
1--15
Opis fizyczny
bibliogr. 12 poz.
Twórcy
autor
autor
autor
  • Research Group on Mathematical Linguistics Rovira I Virgili University Pl. Imperial Tarraco 1, 43005 Tarragona, Spain, cmv@astor.urv.es
Bibliografia
  • [1] B. Alberts et al., Essential Cell Biology. A n Introduction to the Molecular Biology of the Cell, Garland Publ. Inc., New York, London, 1998.
  • [2] J. Dassow, Gh. P5un, Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.
  • [3] R. Freund, Gh. PSun, On the number of non-terminals in graph-controlled, programmed, and matrix gram ¬mars, Proc. Third. Intern. Conf, on Universal Machines and Computations, Chigin&u, Moldova, 2001, Lect. Notes in Computer Science, 2055 (M. Margenstem, Y. Rogozhin, eds.), Springer-Verlag, 2001, 214-225 .
  • [4] C. Martin-Vide, A. Pdun, Gh. Paun, On the power of P systems with symport rules, J. Univ. Computer Sci., 2002.
  • [5] C. Martin-Vide, Gh. PSun, G. Rozenberg, Membrane systems with carriers, Theoretical Computer Sci., to appear.
  • [6] A. Paun, Gh. Paun, The power of communication: P systems with symport/antiport, New Generation Computers, to appear.
  • [7] A. Paun, Gh. P3un, A. Rodriguez-Paton, Further remarks on P systems with symport rules, Annals of AU. Cuza Univ., Iassy, Mathematics-Informatics Series, 2001.
  • [8] Gh. Paun, Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108-143, and Turku Center for Computer Science-TUCS Report No 208, 1998 (www.tucs.fi).
  • [9] Gh. Paun, Computing with membranes; Attacking NP-complete problems, in vol. Unconventional Models of Computation (I. Antoniou, C.S. Calude, M.J. Dinneen, eds.), Springer-Verlag, London, 2000,94-115.
  • [10] Gh. Paun, G. Rozenberg, A guide to membrane computing, Theoretical Computer Science, to appear.
  • [11] G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, 3 volumes, Springer-Verlag, Berlin, 1997.
  • [12] Cl. Zandron, Cl. Ferretti, G. Mauri, Solving NP-complete problems using P systems with active membranes, in vol. Unconventional Models of Computation (I. Antoniou, C.S. Calude, M.J. Dinneen, eds.), Springer- Verlag, London, 2000, 289-301.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0003-0097
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.