P Systems with Replicated Rewriting and Stream X-Machines (Eilenberg Machines)

• Autorzy: Aguado, J. , Balanescu, T. , Cowling, T. , Gheorghe, M. , Holcombe, M. , Ipate, F.
• Języki publikacji: EN

Abstrakty

EN

The aim of this paper is to show how the P systems with replicated rewriting can be modeled by X-machines (also called Eilenberg machines). In the first approach, the parallel behaviour of the regions of a P system is simulated by a sequential process involving a single X-machine. This allows the application of the X-machine testing procedures in order to prove the correctness of P systems. In the second approach, a P system is simulated by a communicating system of X-machines. Each component of such a system is an X-machine associated with a region of the given P system. The components act in parallel, as their counterparts do in a P system, and use some specific mechanism for communication and synchronisation.

Słowa kluczowe

EN

P systems; finite state machine; stream X-machines; formal specifications

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 49, nr 1-3
• Strony: 17-33
• Opis fizyczny: bibliogr. 16 poz.

Twórcy

autor

Aguado, J.

autor

Balanescu, T.

autor

Cowling, T.

autor

Gheorghe, M.

autor

Holcombe, M.

autor

Ipate, F.

• Department of Computer Science, Sheffeld University, Regent Court, Portobello Street, Sheffield, SI 4DP, UK

Bibliografia

• [1] T. B&lSnescu, T. Cowling, H. Georgescu, M. Gheorghe, M Holcombe, C. Vertan, Communicating stream X-machine are no more than X-machine, J.UCS, 5(9), 1999,494-507.
• [2] T. B&lSnescu, M. Gheorghe, A set of string functions and its power, Annals of Bucharest University, XCV(l) (1996), 9-14.
• [3] T. B&lSnescu, H. Georgescu, M. Gheorghe, Stream X-machine with underlying distributed grammars, Infor-matica, submitted 2001.
• [4] E. Csuhaj-Varju, J. Dassow, J. Kelemen, Gh. P2un, Grammar Systems. A Grammatical Approach to Distri¬bution and Cooperation, Gordon & Breach, London, 1994.
• [5] S. Eilenberg, Automata, Languages and Machines, Academic Press, 1974. [6] M. Gheorghe, Generalised stream X-machines and cooperating distributed grammar systems, Formal Aspects of Computing, 12 (2001), 459-472.
• [7] M. Holcombe, X-machines as a basis for dynamic system specification, Software Engineering Journal, 3(2) (1988), 69-76.
• [8] M. Holcombe, F. Ipate, Correct Systems: Building a Business Process Solution, Springer-Verlag, Berlin, 1998.
• [9] F. Ipate, M. Holcombe, An integration testing method that is proved to find all faults, Intern. J. Computer Math, 63 (1997), 159-178.
• [10] F. Ipate, M. Holcombe, Testing conditions for communicating stream X-machine systems, Formal Aspects of Computing, 2001, to appear.
• [11] S. N. Krishna, R. Rama, P systems with replicated rewriting, J. Automata, Languages, Combinatorics, to appear.
• [12] V. Manca, C. Martin-Vide, Gh. P2un, On the power of P systems with replicated rewriting, J. Automata, Languages, Combinatorics, to appear.
• [13] C. Martin-Vide, Gh. Paun, Computing with membranes (P systems): Universality results, Proc. Third. Intern. Conf, on Universal Machines and Computations, Chi§in3u, Moldova, 2001, Lect. Notes in Computer Science, 2055 (M. Margenstem, Y. Rogozhin, eds.), Springer-Verlag, 2001, 82-101.
• [14] Gh. Paun, Computing with membranes, J of Computer and System Sciences, 61, 1 (2000), 108-143.
• [15] D. Peleg, Complexity Considerations for Distributed Data Structures, Technical Report CS89-31, Depart¬ment of Applied Mathematics and Computer Science, The Weizmann Institute of Science, 1989.
• [16] G. Tei, Distributed Algorithms, Cambridge University Press, 2000.