Testing Semantics for RTPA

• Autorzy: Llana L. , Núnez M.
• Języki publikacji: EN

Abstrakty

EN

The language RTPA, Real Time Process Algebra, has been created to enable rigorous treatment of knowledge representation and manipulation in terms of to be I to have / to do in a formal and coherent framework. This language has been designed to cope with the three dimensions involved in the problem of software specification: (i) mathematical operations, (ii) event/process timing, and (iii) memory manipulation. In this paper we focus on giving a testing semantics to the second dimension: Process timing dimension. First, we will provide a SOS like operational semantics for the process relations of RTPA. Next, we will define what a test is and we will introduce a relation based on which tests are passed by processes. Finally, we will obtain an operational characterization that can be used as a first step to define a denotational sematics sound and complete with respect the testing semantics.

Słowa kluczowe

EN

RTPA; real time process algebra; testing semantics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 90, nr 3
• Strony: 305--335
• Opis fizyczny: bibliogr. 45 poz., tab.

Twórcy

autor

Llana L.

autor

Núnez M.

• Dpto. Sistemas Inform´aticos y Computación. Universidad Complutense de Madrid. 28040 Madrid. Spain,

Bibliografia

• [1] J.C.M. Baeten and C.A. Middelburg. Process algebra with timing. EATCS Monograph. Springer, 2002.
• [2] J.C.M. Baeten and W.P. Weijland. Process Algebra. Cambridge Tracts in Computer Science 18. Cambridge University Press, 1990.
• [3] J.A. Bergstra, A. Ponse, and S.A. Smolka, editors. Handbook of Process Algebra. North Holland, 2001.
• [4] M. Bernardo and R. Gorrieri. A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time. Theoretical Computer Science, 202(1-2):1-54, 1998.
• [5] M. Bravetti and R. Gorrieri. The theory of interactive generalized semi-Markov processes. Theoretical Computer Science, 282(1):5-32, 2002.
• [6] D. Cazorla, F. Cuartero, V. Valero, F.L. Pelayo, and J.J. Pardo. Algebraic theory of probabilistic and nondeterministic processes. Journal of Logic and Algebraic Programming, 55(1-2):57-103, 2003.
• [7] R. Cleaveland, Z. Dayar, S.A. Smolka, and S. Yuen. Testing preorders for probabilistic processes. Information and Computation, 154(2):93-148, 1999.
• [8] J. Davies and S. Schneider. A brief history of timed CSP. Theoretical Computer Science, 138:243-271, 1995.
• [9] R. de Nicola and M.C.B. Hennessy. Testing equivalences for processes. Theoretical Computer Science, 34:83-133, 1984.
• [10] R. van Glabbeek, S.A. Smolka, and B. Steffen. Reactive, generative and stratified models of probabilistic processes. Information and Computation, 121(1):59-80, 1995.
• [11] N. Gőtz, U. Herzog, and M. Rettelbach. Multiprocessor and distributed system design: The integration of functional specification and performance analysis using stochastic process algebras. In 16th Int. Symp. On Computer Performance Modelling, Measurement and Evaluation, PERFORMANCE'93, LNCS 729, pages 121-146. Springer, 1993.
• [12] J. F. Groote. Transition system specifications with negative premises. Theoretical Computer Science, 118:263-299, 1993.
• [13] P.G. Harrison and B. Strulo. SPADES - a process algebra for discrete event simulation. Journal of Logic Computation, 10(1):3-42, 2000.
• [14] M. Hennessy. Algebraic Theory of Processes. MIT Press, 1988.
• [15] J. Hillston. A Compositional Approach to Performance Modelling. Cambridge University Press, 1996.
• [16] C.A.R. Hoare. Communicating Sequential Processes. Prentice Hall, 1985.
• [17] L. Llana and D. de Frutos. Denotational semantics for timed testing. In 4th AMAST Workshop on Real-Time Systems, Concurrent and Distributed Software, LNCS 1231, pages 368-382, 1997.
• [18] L. Llana and D. de Frutos. Relating may and must testing semantics for discrete timed process algebras. In 5th Asian Computing Science Conference, ASIAN'99, LNCS 1742, pages 74-86. Springer, 1999.
• [19] N. López and M. Núñez. A testing theory for generally distributed stochastic processes. In 12th Int. Conf. on Concurrency Theory, CONCUR'01, LNCS 2154, pages 321-335. Springer, 2001.
• [20] N. López, M. Núñez, and F.L. Pelayo. STOPA: A STOchastic Process Algebra for the formal representation of cognitive systems. In 3rd IEEE Int. Conf. on Cognitive Informatics, ICCI'04, pages 64-73. IEEE Computer Society Press, 2004.
• [21] N. López,M. Núñez, and F.L. Pelayo. Specifying the memorization process with STOPA. The International Journal of Cognitive Informatics & Natural Intelligence, 1(4):47-60, 2007.
• [22] N. López, M. Núñez, I. Rodr´ıguez, and F. Rubio. A formal framework for e-barter based on microeconomic theory and process algebras. In Innovative Internet Computer Systems, LNCS 2346, pages 217-228. Springer, 2002.
• [23] N. López,M. Núñez, and F. Rubio. An integrated framework for the analysis of asynchronous communicating stochastic processes. Formal Aspects of Computing, 16(3):238-262, 2004.
• [24] R. Milner. Communication and Concurrency. Prentice Hall, 1989.
• [25] R. Milner. Communicating and Mobile Systems: the _-Calculus. Cambridge University Press, 1999.
• [26] X. Nicollin and J. Sifakis. An overview and synthesis on timed process algebras. In 3rd Int. Conf. on Computer Aided Verification, CAV'91, LNCS 575, pages 376-398. Springer, 1991.
• [27] M. Núñez. Algebraic theory of probabilistic processes. Journal of Logic and Algebraic Programming, 56(1-2):117-177, 2003.
• [28] M. Núñez and D. de Frutos. Testing semantics for probabilistic LOTOS. In 8th IFIP WG6.1 Int. Conf. on Formal Description Techniques, FORTE'95, pages 365-380. Chapman & Hall, 1995.
• [29] M. Núñez, D. de Frutos, and L. Llana. Acceptance trees for probabilistic processes. In 6th Int. Conf. on Concurrency Theory, CONCUR'95, LNCS 962, pages 249-263. Springer, 1995.
• [30] M. Núñez and I. Rodrıguez. PAMR: A process algebra for the management of resources in concurrent systems. In 21st IFIP WG 6.1 Int. Conf. on Formal Techniques for Networked and Distributed Systems, FORTE'01, pages 169-185. Kluwer Academic Publishers, 2001.
• [31] M. Núñez, I. Rodr´ıguez, and F. Rubio. Formal specification of multi-agent e-barter systems. Science of Computer Programming, 57(2):187-216, 2005.
• [32] F. L. Pelayo, F. Cuartero, V. Valero, and D. Cazorla. An example of performance evaluation by using the stochastic process algebra ROSA. In 7th Int. Conf. on Real-Time Systems and Applications, pages 271-278. IEEE Computer Society Press, 2000.
• [33] F.L. Pelayo, M. Núñez, and N. López. Specifying the memorization process with STOPA. In 4th IEEE Int. Conf. on Cognitive Informatics, ICCI'05, pages 238-247. IEEE Computer Society Press, 2005.
• [34] G.M. Reed and A.W. Roscoe. A timed model for communicating sequential processes. Theoretical Computer Science, 58:249-261, 1988.
• [35] Xinming Tan and YingxuWang. A denotational semantics for RTPA. Electrical and Computer Engineering, 2005. Canadian Conference on, pages 2057-2060,May 2005.
• [36] Y. Wang. On cognitive informatics. In 1st IEEE Int. Conf. on Cognitive Informatics, ICCI'02, pages 34-42. IEEE Computer Society Press, 2002.
• [37] Y. Wang. The Real Time Process Algebra (RTPA). Annals of Software Engineering, 14:235-274, 2002.
• [38] Y. Wang. Cognitive informatics: A new transdisciplinary research field. Brain and Mind, 4:115-127, 2003.
• [39] Y. Wang. Using process algebra to describe human and software behaviors. Brain and Mind, 4:199-213, 2003.
• [40] Y. Wang. On the mathematical laws of software. In 18th Canadian Conf. on Electrical and Computer Engineering, CCECE'05, pages 1086-1089, 2005.
• [41] Y. Wang. Cognitive informatics and contemporary mathematics for knowledge manipulation. In Guoyin Wang, James F. Peters, Andrzej Skowron, and Yiyu Yao, editors, RSKT, volume 4062 of Lecture Notes in Computer Science, pages 69-78. Springer, 2006.
• [42] Y. Wang. The theoretical framework of cognitive informatics. The International Journal of Cognitive Informatics & Natural Intelligence, 1(1):1-27, 2007.
• [43] Y. Wang, L. Dong, and G. Ruhe. Formal description of the cognitive process of decision making. In 3rd IEEE Int. Conf. on Cognitive Informatics, ICCI'04, pages 124-130. IEEE Computer Society Press, 2004.
• [44] Y. Wang and Y. Wang. Recent advances in cognitive informatics. IEEE Transactions on Systems, Man, and Cybernetics C, 36(2):121-123, 2006.
• [45] W. Yi. CCS+ Time = an interleaving model for real time systems. In 18th Int. Colloquium on Automata, Languages and Programming, ICALP'91, LNCS 510, pages 217-228. Springer, 1991.