TY - GEN
T1 - On the expressive power of temporal concurrent constraint programming languages
AU - Nielsen, Mogens
AU - Palamidessi, Catuscia
AU - Valencia, Frank D.
PY - 2002/1/1
Y1 - 2002/1/1
N2 - 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.
AB - 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.
KW - Constraint programming
KW - Expressiveness
KW - Timed systems
UR - https://www.scopus.com/pages/publications/0036989084
U2 - 10.1145/571157.571173
DO - 10.1145/571157.571173
M3 - Conference contribution
AN - SCOPUS:0036989084
SN - 1581135289
SN - 9781581135282
T3 - Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)
SP - 156
EP - 167
BT - Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)
PB - Association for Computing Machinery (ACM)
T2 - Proceedings of the Fourth ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)
Y2 - 6 October 2002 through 8 October 2002
ER -