Carriers and Counters
作者： Hendrik Jan Hoogeboom
关键词: Automaton 、 Turing machine 、 Default rule 、 Parallel computing 、 Computer science 、 Parallelism (grammar) 、 Power (physics)
摘要: P systems with carriers are shown to be computationally complete only a single membrane and two carriers. We argue that their power is due the maximal parallelism required in application of rules. In fact, carrier, these equivalent blind counter automata. Finally, passenger restriction again complete.
springer.com
sci-hub.st 参考文章(10)
Hans-Dieter Burkhard, Ordered Firing in Petri Nets Journal of Automata, Languages and Combinatorics. ,vol. 17, pp. 71- 86 ,(1981) , 10.18452/9413
Pierluigi Frisco, Hendrik Jan Hoogeboom, Simulating Counter Automata by P Systems with Symport/Antiport Lecture Notes in Computer Science. pp. 288- 301 ,(2002) , 10.1007/3-540-36490-0_19
Rudolf Freund, Gheorghe Păun, On the Number of Non-terminal Symbols in Graph-Controlled, Programmed and Matrix Grammars machines computations and universality. pp. 214- 225 ,(2001) , 10.1007/3-540-45132-3_14
Rajeev Motwani, John E. Hopcroft, Jeffrey D. Ullman, Rotwani, Introduction to Automata Theory, Languages, and Computation ,(1979)
Dirk Hauschildt, Matthias Jantzen, Petri net algorithms in the theory of matrix grammars Acta Informatica. ,vol. 31, pp. 719- 728 ,(1994) , 10.1007/BF01178731
S.A. Greibach, Remarks on blind and partially blind one-way multicounter machines Theoretical Computer Science. ,vol. 7, pp. 311- 324 ,(1978) , 10.1016/0304-3975(78)90020-8
Carlos Martı́n-Vide, Gheorghe Păun, Grzegorz Rozenberg, Membrane systems with carriers Theoretical Computer Science. ,vol. 270, pp. 779- 796 ,(2002) , 10.1016/S0304-3975(01)00117-7
Gheorghe Paun, Membrane Computing: An Introduction ,(2002)
Gheorghe Păun, Computing with Membranes Journal of Computer and System Sciences. ,vol. 61, pp. 108- 143 ,(2000) , 10.1006/JCSS.1999.1693
Carlos Martín-Vide, Gheorghe PĂun, Computing with Membranes (P Systems): Universality Results machines computations and universality. pp. 82- 101 ,(2001) , 10.1007/3-540-45132-3_5