On the expressive power of temporal concurrent constraint programming languages

ABSTRACT

The tcc paradigm is a formalism for timed concurrent constraint programming. Several tcc languages differing in their way of expressing infinite behavior have been proposed in the literature. In this paper we study the expressive power of some of these languages. In particular, we show that: (1) recursive procedures with parameters can be encoded into parameterless recursive procedures with dynamic scoping, and viceversa. (2) replication can be encoded into parameterless recursive procedures with static scoping, and viceversa. (3) the languages from (1) are strictly more expressive than the languages from (2). Furthermore, we show that behavioral equivalence is undecidable for the languages from (1), but decidable for the languages from (2). The undecidability result holds even if the process variables take values from a fixed finite domain.

REFERENCES

• 1: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V]
• 2: J. R. Buchi. On a decision method in restricted second order arithmetic. In Proc. Int. Cong. on Logic, Methodology, and Philosophy of Science, pages 1--11. Stanford University Press, 1962.
• 3: F. S. de Boer , M. Gabbrielli , M. C. Meo, A timed concurrent constraint language, Information and Computation, v.161 n.1, p.45-83, Aug. 25, 2000 [doi>10.1006/inco.1999.2879]
• 4: Frank S. De Boer , Maurizio Gabbrielli , Elena Marchiori , Catuscia Palamidessi, Proving concurrent constraint programs correct, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.5, p.685-725, Sept. 1997 [doi>10.1145/265943.265954]
• 5: N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous data-flow programming language LUSTRE. Proceedings of the IEEE, 79(9):1305--1320, 1991.
• 6: Florence Maraninchi, Operational and Compositional Semantics of Synchronous Automaton Compositions, Proceedings of the Third International Conference on Concurrency Theory, p.550-564, August 24-27, 1992
• 7: Nax P. Mendler , Prakash Panangaden , P. J. Scott , R. A. G. Seely, A logical view of concurrent constraint programming, Nordic Journal of Computing, v.2 n.2, p.181-220, Summer 1995
• 8: R. Milner, Communication and concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 9: Robin Milner, Communicating and mobile systems: the &pgr;-calculus, Cambridge University Press, New York, NY, 1999
• 10: Mogens Nielsen , Frank D. Valencia, Temporal Concurrent Constraint Programming: Applications and Behavior, Formal and Natural Computing - Essays Dedicated to Grzegorz Rozenberg [on occasion of his 60th birthday, March 14, 2002], p.298-324, March 14, 2002
• 11: M. Nielsen, C. Palamidessi, and F. Valencia. On the expressive power of concurrent constraint programming languages. Tech. Report RS-02-22, BRICS, University of Aarhus.
• 12: Catuscia Palamidessi , Frank D. Valencia, A Temporal Concurrent Constraint Programming Calculus, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.302-316, November 26-December 01, 2001
• 13: E. L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52:264--268, 1946.
• 14: Vijay A. Saraswat, Concurrent constraint programming, MIT Press, Cambridge, MA, 1993
• 15: V. Saraswat, R. Jagadeesan, and V. Gupta. Foundations of timed concurrent constraint programming. In Proc. of the IEEE Symp. on Logic in Computer Science, pages 71--80. IEEE Computer Society Press, 1994.
• 16: V. Saraswat, R. Jagadeesan, and V. Gupta. Programming in timed concurrent constraint languages. In Constraint Programming, volume 131 of NATO ASI Sub-series F: Computer and System Sciences, Ch. 4, pages 361--410. Springer-Verlag, 1994.
• 17: Vijay Saraswat , Radha Jagadeesan , Vineet Gupta, Timed default concurrent constraint programming, Journal of Symbolic Computation, v.22 n.5-6, p.475-520, Nov./Dec. 1996 [doi>10.1006/jsco.1996.0064]
• 18: Vijay A. Saraswat , Martin Rinard , Prakash Panangaden, The semantic foundations of concurrent constraint programming, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-352, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99627]
• 19: J. R. Shoenfield. Mathematical Logic. Addison-Wesley Publishing Company, 1967.
• 20: A. Prasad Sistla , M. Y. Vardi , P. Wolper, The complementation problem for Bu¨chi automata with applications to temporal logic, Theoretical Computer Science, v.49 n.2-3, p.217-237, January 1987 [doi>10.1016/0304-3975(87)90008-9]
• 21: S. Tini. On the expressiveness of timed concurrent constraint programming. Electronics Notes in Theoretical Computer Science, 1999.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes

General Terms:
Languages, Theory

Keywords:
constraint programming, expressiveness, timed systems