@inproceedings{6986ac06f6024cfab19fae04e1a02dd7,
title = "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.",
keywords = "Constraint programming, Expressiveness, Timed systems",
author = "Mogens Nielsen and Catuscia Palamidessi and Valencia, \{Frank D.\}",
year = "2002",
doi = "10.1145/571157.571173",
language = "English",
isbn = "1581135289",
series = "Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)",
publisher = "Association for Computing Machinery (ACM)",
pages = "156--167",
booktitle = "Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02)",
address = "United States",
note = "Proceedings of the Fourth ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP'02) ; Conference date: 06-10-2002 Through 08-10-2002",
}