Behavioral complexity indicators for process algebra: the NKS approach
Bolognesi T.
Elementary cellular automata Complexity indicator Computational Theory and Mathematics Process algebra Turing completeness Pseudo-random number generator Theoretical Computer Science NKS Models of Computation Software Logic
Several techniques for the experimental investigation of the computing power of various formal models, from cellular automata to Turing machines, have been proposed by S.Wolfram with his NKS (New Kind of Science). Visual complexity indicators reveal the 'internal shapes' of computations, and may expose constant, periodic, nested/fractal, pseudo-random, and even more sophisticated dynamics. In this paper we investigate visual complexity indicators for process algebra. With its emphasis on reactive, continuously observable behavior, as opposed to input/output behavior, process algebra might appear as an ideal candidate for NKS-style investigations; however, this formal model is in some sense more elaborate than the simple formalisms addressed in NKS, and poses specific problems, such as the presence of both events and states, and the explosive nature of non-determinism. We consider a set of process algebraic operators and prove its Turing universality by showing that they can emulate any elementary cellular automaton, including n. 110, which is itself universal. The correctness of the emulation is supported by an original visual indicator, which is then used for exploring various subclasses of algebraic expressions and their emergent features. Based on this indicator, and even by restricting to deterministic computations, we have detected and measured, by a data compression technique, the emergence of randomness in a subclass of expressions which is provably not universal. Besides providing a suggestive visualization of the relative strengths of operator subsets, we believe that results of this type, both of theoretical and of experimental nature, are desirable in light of one of the key NKS conjectures, according to which random-like behavior would be a witness of computational universality.
Source: The journal of logic and algebraic programming 72 (2007): 50–77. doi:10.1016/j.jlap.2007.02.004
Publisher: North-Holland,, New York, N.Y. , Stati Uniti d'America
[2] R. Milner, Communication and Concurrency, Prentice-Hall, 1989.
[3] C.A.R. Hoare, Communicating Sequential Processes, Prentice Hall, 1985.
[4] J. Bergstra, J.W. Klop, Process algebra for synchronous communication, Inform. and Control 60 (1-3) (1984) 109-137.
[5] E. Brinksma, T. Bolognesi, Introduction to the ISO specification language LOTOS, Comput. Networks ISDN Syst. 14 (1) (1987) 25-59.
[6] R. Milner, Four combinators for concurrency, PODC'82: Proceedings of the First ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, ACM Press, New York, NY, USA, 1982, pp. 104-110.
[7] U. Goltz, A. Mycroft, On the relationship of CCS and Petri Nets, Proceedings of the 11th Colloquium on Automata, Languages and Programming, Springer-Verlag, London, UK, 1984, pp. 196-208.
[8] R. Milner, Lecture Notes in Computer Science, Springer-Verlag, 1980.
[9] D.E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, third ed., Addison-Wesley, 1997.
[10] K. Sutner, Universality and cellular automata, Proceedings of MCU 2005, LNCS 3354, vol. 92, Springer-Verlag, Berlin, Heidelberg, 2005, pp. 50-59.
[11] M. Davis, The definition of universal Turing machines, Proc. Amer. Math. Soc. 8 (1957) 1125-1126.
[12] F.W. Vaandrager, Expressive results for process algebras, in: J.W. de Bakker, W.P. de Roever, G. Rozenberg (Eds.), REX Workshop, Lecture Notes in Computer Science, vol. 666, Springer, 1992, pp. 609-638.
[13] T. Bolognesi, Process algebra under the light of Wolfram's NKS, in: A. Gordon, L. Aceto (Eds.), Proceedings of the Workshop 'Essays on Algebraic Process Calculi' (APC 2005), Electronic Notes in Theoretical Computer Science, vol. 162, Elsevier, 2006, pp. 101-105.
[14] J.F. Groote, F. van Ham, Large state space visualization, in: H. Garavel, J. Hatcliff (Eds.), TACAS, Lecture Notes in Computer Science, vol. 2619, Springer, 2003, pp. 585-590.
[15] R. Milner, J. Parrow, D. Walker, A calculus of mobile processes, (Parts I and II), Inform. Comput. 100 (1992) 1-77.
[16] C. Palamidessi, Comparing the expressive power of the synchronous and the asynchronous pi-calculus, POPL'97: Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ACM Press, New York, NY, USA, 1997, pp. 256-265.
[17] N. Yoshida, Minimality and separation results on asynchronous mobile processes - representability theorems by concurrent combinators, Theor. Comput. Sci. 274 (2002) 231-276.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:43974,
title = {Behavioral complexity indicators for process algebra: the NKS approach},
author = {Bolognesi T.},
publisher = {North-Holland,, New York, N.Y. , Stati Uniti d'America},
doi = {10.1016/j.jlap.2007.02.004},
journal = {The journal of logic and algebraic programming},
volume = {72},
pages = {50–77},
year = {2007}
}
0000-0003-0854-2587
