Making Random Choices Invisible to the Scheduler (2010)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to resolve the nondeterminism. It...
Making Random Choices Invisible to the Scheduler (2010)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to resolve the nondeterminism. It...
Probable innocence in the presence of independent knowledge (2009)
Hamadou, Sardaouna, Palamidessi, Catuscia, Sassone, Vladimiro, ElSalamouny, Ehab
We analyse the Crowds anonymity protocol under the novel assumption that the attacker has independent knowledge on behavioural patterns of individual users. Under such conditions we study,...
On the Bayes Risk in Information-Hiding Protocols ∗ (2009)
Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden
Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a...
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1 Model (2009)
Gethin Norman, Catuscia Palamidessi, David Parker, Peng Wu
checking probabilistic and stochastic extensions of the π-calculus
Frank S. De, Utrecht Maurizio, Pisa Elena, Catuscia Palamidessi
fl store-as-valuation
Compositional Methods for Information-Hiding ⋆ (2009)
Christelle Braun, Konstantinos Chatzikokolakis, Catuscia Palamidessi
Abstract. Protocols for information-hiding often use randomized primitives to obfuscate the link between the observables and the information to be protected. The degree of protection provided by a...
Formal approaches to Information-Hiding – A tutorial ⋆ – (2009)
Romain Beauxis, Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden
Abstract. In this survey paper we consider the class of protocols for informationhiding which use randomization to obfuscate the link between the observables and the information to be protected. We...
Romain Beauxis, Catuscia Palamidessi, Frank D. Valencia, Inria Saclay, École Polytechnique
the asynchronous nature of the asynchronous
Expressiveness of Recursion, Replication and Scope Mechanisms in Process Calculi (2009)
Catuscia Palamidessi, Frank D. Valencia
Process calculi such as CCS [Mil89], the π-calculus [MPW92] and Ambients [CG00] are among the most in uential formal methods for modelling and analyzing the behaviour of concurrent systems; i.e....
Axelle Ziegler, Dale Miller, Catuscia Palamidessi
congruence format for name-passing calculi
A Probabilistic Applied Pi–Calculus ⋆ (2009)
Jean Goubault-larrecq, Catuscia Palamidessi, Angelo Troina
Abstract. We propose an extension of the Applied Pi–calculus by introducing nondeterministic and probabilistic choice operators. The semantics of the resulting model, in which probability and...
On Recursion, Replication and Scope Mechanisms in Process Calculi (2009)
Jesús Ar, Cinzia Di Giusto, Catuscia Palamidessi, Frank D. Valencia
Abstract. In this paper we shall survey and discuss in detail the work on the relative expressiveness of recursion and replication in various process calculi. Namely, CCS, the π-calculus, the...
2Dipartimento di Informatica e Scienze dell'Informazione, (2009)
Ra Di Pierro, Maurizio Martelli, Catuscia Palamidessi
A `7\Gamma!\Lambda 2) P j = 8A ` (soundness of success)
Probable Innocence and Independent Knowledge (2009)
Hamadou, Sardaouna, Palamidessi, Catuscia, Sassone, Vladimiro, Elsalamouny, Ehab
We analyse the \textsc{Crowds} anonymity protocol under the novel assumption that the attacker has independent knowledge on behavioural patterns of individual users. Under such conditions we study,...
Probable Innocence and Independent Knowledge (2009)
Hamadou, Sardaouna, Palamidessi, Catuscia, Sassone, Vladimiro, Elsalamouny, Ehab
We analyse the \textsc{Crowds} anonymity protocol under the novel assumption that the attacker has independent knowledge on behavioural patterns of individual users. Under such conditions we study,...
Model checking probabilistic and stochastic extensions of the $\pi$-calculus (2009)
Norman, Gethin, Palamidessi, Catuscia, Parker, David, Wu, Peng
We present an implementation of model checking for probabilistic and stochastic extensions of the -calculus, a process algebra which supports modelling of concurrency and mobility. Formal...
Probabilistic and nondeterministic aspects of anonymity (2009)
Beauxis, Romain, Palamidessi, Catuscia
The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending emails. The protocols for ensuring...
Quantitative Notions of Leakage for One-try Attacks (2009)
Braun, Christelle, Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
Recent research in quantitative theories for information-hiding topics, such as Anonymity and Secure Information Flow, tend to converge towards the idea of modeling the system as a noisy channel in...
Model checking probabilistic and stochastic extensions of the $\pi$-calculus (2009)
Norman, Gethin, Palamidessi, Catuscia, Parker, David, Wu, Peng
We present an implementation of model checking for probabilistic and stochastic extensions of the -calculus, a process algebra which supports modelling of concurrency and mobility. Formal...
Probabilistic and nondeterministic aspects of anonymity (2009)
Beauxis, Romain, Palamidessi, Catuscia
The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending emails. The protocols for ensuring...
Quantitative Notions of Leakage for One-try Attacks (2009)
Braun, Christelle, Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
Recent research in quantitative theories for information-hiding topics, such as Anonymity and Secure Information Flow, tend to converge towards the idea of modeling the system as a noisy channel in...
A Framework for Abstract Interpretation of Timed Concurrent Constraint Programs (2009)
Falaschi, Moreno, Olarte, Carlos, Palamidessi, Catuscia
Timed Concurrent Constraint Programming (tcc) is a declarative model for concurrency offering a logic for specifying reactive systems, i.e. systems that continuously interact with the environment....
A Framework for Abstract Interpretation of Timed Concurrent Constraint Programs (2009)
Falaschi, Moreno, Olarte, Carlos, Palamidessi, Catuscia
Timed Concurrent Constraint Programming (tcc) is a declarative model for concurrency offering a logic for specifying reactive systems, i.e. systems that continuously interact with the environment....
SecCo 2005 Preliminary Version Weak Probabilistic Anonymity 1 (2008)
Yuxin Deng, Catuscia Palamidessi, Jun Pang, Inria Futurs
Abstract Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Languages for Concurrency (2008)
Catuscia Palamidessi, Frank D. Valencia
This essay offers an overview of basic aspects and central development in Concurrency Theory based on formal languages. In particular, it focuses on the theory of Process Calculi. 1
A Probabilistic Applied Pi–Calculus ⋆ (2008)
Jean Goubault-larrecq, Catuscia Palamidessi, Angelo Troina
Abstract. We propose an extension of the Applied Pi–calculus by introducing nondeterministic and probabilistic choice operators. The semantics of the resulting model, in which probability and...
On the Bayes Risk in Information-Hiding Protocols ∗ (2008)
Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden
Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a...
MFPS XX1 Preliminary Version Probabilistic and nondeterministic aspects of Anonymity 1 (2008)
Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Anonymity in probabilistic and nondeterministic systems 1 (2008)
Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Mogens Nielsen, Frank D. Valencia, Catuscia Palamidessi
Abstract. The tcc model is a formalism for reactive concurrent constraint programming. We present a model of temporal concurrent constraint programming which adds to tcc the capability of modeling...
Christelle Braun, Konstantinos Chatzikokolakis, Catuscia Palamidessi, École Polytechnique
Protocols for information-hiding often use randomized primitives to obfuscate the link between the observables and the information to be protected. The degree of protection provided by a protocol can...
Symbolic Bisimulations for Probabilistic Systems (2008)
Peng Wu, Catuscia Palamidessi, Huimin Lin
The paper introduces symbolic bisimulations for a simple probabilistic π-calculus to overcome the infinite branching problem that still exists in checking ground bisimulations between probabilistic...
Universal Timed Concurrent Constraint Programming (2008)
Carlos Olarte, Catuscia Palamidessi, Frank Valencia, Inria Futurs, École Polytechnique
Abstract In this doctoral work we aim at developing a rich timed concurrent constraint (tcc) based language with strong ties to logic. The new calculus called Universal Timed Concurrent Constraint...
Symbolic Bisimulations for Probabilistic Systems (2008)
Peng Wu, Catuscia Palamidessi, Huimin Lin
The paper introduces symbolic bisimulations for a simple probabilistic π-calculus to overcome the infinite branching problem that still exists in checking ground bisimulations between probabilistic...
Catuscia Palamidessi, Vijay Saraswat, Frank Valencia, Bjorn Victor
We present an expressiveness study of linearity and persistence of processes. We choose the π-calculus, one of the main representatives of process calculi, as a framework to conduct our study. We...
A Declarative Framework for Security: Secure Concurrent Constraint Programming (2008)
Hugo A. López, Catuscia Palamidessi, Jorge A. Pérez, Camilo Rueda, Frank D. Valencia
Motivation. Due to technological advances such as the Internet and mobile computing, Security has become a serious challenge involving several disciplines of Computer Science. In recent years, there...
– Output prefix – Blind choice – Input-guarded choice (2008)
Catuscia Palamidessi, Separation Results
Content of the slides / Plan of the lecture • Discussion on the notion of expressiveness – encoding • Encoding some of the features of the synchronous π-calculus into the asynchronous...
Abstract SecCo 2005 Preliminary Version Weak Probabilistic Anonymity 1 (2008)
Yuxin Deng, Inria Sophia-antipolis, Catuscia Palamidessi, Jun Pang, Inria Futurs, ...
Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
On the Bayes Risk in Information-Hiding Protocols ∗ (2008)
Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden
Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a...
Probabilistic Timed Automata for Security Analysis and Design (2008)
Angelo Troina, Supervisor Prof, Andrea Maggiolo Schettini, Referee Prof, Catuscia Palamidessi, Referee Prof, ...
4 Abstract The usefulness of formal methods for the description and verification of complex systems is nowa-days widely accepted. While some system properties can be studied in a non-timed and...
Abstract SecCo 2005 Preliminary Version Weak Probabilistic Anonymity 1 (2008)
Yuxin Deng, Inria Sophia-antipolis, Catuscia Palamidessi, Jun Pang, Inria Futurs, ...
Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
A Probabilistic Applied Pi–Calculus ⋆ (2008)
Jean Goubault-larrecq, Catuscia Palamidessi, Angelo Troina
Abstract. We propose an extension of the Applied Pi–calculus by introducing nondeterministic and probabilistic choice operators. The semantics of the resulting model, in which probability and...
Formal Approaches to Information-Hiding (Tutorial) (2008)
Beauxis, Romain, Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
In this survey paper we consider the class of protocols for information-hiding which use randomization to obfuscate the link between the observables and the information to be protected. We focus on...
Formal Approaches to Information-Hiding (Tutorial) (2008)
Beauxis, Romain, Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
In this survey paper we consider the class of protocols for information-hiding which use randomization to obfuscate the link between the observables and the information to be protected. We focus on...
Compositional Methods for Information-Hiding (2008)
Braun, Christelle, Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
Protocols for information-hiding often use randomized primitives to obfuscate the link between the observables and the information to be protected. The degree of protection provided by a protocol can...
On the asynchronous nature of the asynchronous π-calculus (2008)
Beauxis, Romain, Palamidessi, Catuscia, Valencia, Frank
We address the question of what kind of asynchronous com- munication is exactly modeled by the asynchronous pi-calculus (pi_a). To this purpose we define a calculus pi_B where channels are...
Anonymity Protocols as Noisy Channels (2008)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
We consider a framework in which anonymity protocols are interpreted as noisy channels in the information-theoretic sense, and we explore the idea of using the notion of capacity as a measure of the...
On the Bayes Risk in Information-Hiding Protocols (2008)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a...
Compositional Methods for Information-Hiding (2008)
Braun, Christelle, Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
Protocols for information-hiding often use randomized primitives to obfuscate the link between the observables and the information to be protected. The degree of protection provided by a protocol can...
On the asynchronous nature of the asynchronous π-calculus (2008)
Beauxis, Romain, Palamidessi, Catuscia, Valencia, Frank
We address the question of what kind of asynchronous com- munication is exactly modeled by the asynchronous pi-calculus (pi_a). To this purpose we define a calculus pi_B where channels are...
Anonymity Protocols as Noisy Channels (2008)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
We consider a framework in which anonymity protocols are interpreted as noisy channels in the information-theoretic sense, and we explore the idea of using the notion of capacity as a measure of the...
On the Bayes Risk in Information-Hiding Protocols (2008)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
Randomized protocols for hiding private information can be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as a...
Jan Willem Klop, Catuscia Palamidessi
) Frank S. de Boer , Jan Willem Klop yz , Catuscia Palamidessi yx Abstract We study the paradigm of asynchronous process communication, as contrasted with the synchronous communication mechanism...
Ra Di Pierro, Catuscia Palamidessi
and infinite computations in constraint programming
Alessandra Di Pierro, Maurizio Martelli, Catuscia Palamidessi
We propose a new negation rule for logic programming which derives existentially closed negative literals, and we define a version of completion for which this rule is sound and complete. The rule is...
Maurizio Gabbrielli, Elena Marchiori, Catuscia Palamidessi
We develop a compositional proof-system for the partial correctness of concurrent constraint programs. Soundness and (relative) completeness of the system are proved with respect to a denotational...
contains no explicit operators for choice and output-prefixing. The communication mechanism of this calculus, however, is powerful enough to simulate output-prefixing, as shown by Honda and Tokoro...
Eike Best, Catuscia Palamidessi
Abstract. In this paper we consider linear constraint programming (lcp), a non-monotonic extension of concurrent constraint programming (ccp) which allows to remove information. The entailment...
contains no explicit operators for choice and output-prefixing. The communication mechanism of this calculus, however, is powerful enough to simulate output-prefixing, as shown by Honda and Tokoro...
Catuscia Palamidessi, Catuscia Palamidessi
Embedding as a tool for Language
and its Application to Concurrent Constraint (2007)
J. N. Kok, J. N. Kok, C. Palamidessi, C. Palamidessi, ...
Communication and its Application
K. R. Apt, E. Marchiori, C. Palamidessi, Krzysztof R. Apt, Elena Marchiori, Catuscia Palamidessi
We provide here a framework for studying Prolog programs with various built-in's that include arithmetic operations, and such metalogical relations like var and ground. To this end we propose a...
Krzysztof R. Apt, Elena Marchiori, Catuscia Palamidessi
z x We provide here a framework for studying Prolog programs with various built-in's that include arithmetic operations, and such metalogical relations like var and ground. To this end we...
A randomized encoding of the-calculus with mixed choice (2007)
Catuscia Palamidessi, Oltea Mihaela Herescu
We consider the problem of encoding the-calculus with mixed choice into the asynchronous-calculus via a uniform translation while preserving a reasonable semantics. Although it has been shown that...
Making Random Choices Invisible to the Scheduler (2007)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to solve the nondeterminism. It has...
Universal Timed Concurrent Constraint Programming (2007)
Olarte, Carlos, Palamidessi, Catuscia, Valencia, Frank
In this doctoral work we aim at developing a rich timed con- current constraint (tcc) based language with strong ties to logic. The new calculus called Universal Timed Concurrent Constraint (utcc)...
Universal Timed Concurrent Constraint Programming (2007)
Olarte, Carlos, Palamidessi, Catuscia, Valencia, Frank
In this doctoral work we aim at developing a rich timed con- current constraint (tcc) based language with strong ties to logic. The new calculus called Universal Timed Concurrent Constraint (utcc)...
Probability of Error in Information-Hiding Protocols (2007)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
Randomized protocols for hiding private information can fruitfully be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as...
Declarative Diagnosis of Temporal Concurrent Constraint Programs (2007)
Falaschi, Moreno, Olarte, Carlos, Palamidessi, Catuscia, Valencia, Frank
We present a framework for the declarative diagnosis of nondeterministic timed concurrent constraint programs. We present a denotational semantics based on a (continuous) immediate consequence...
Weak Probabilistic Anonymity (2007)
Deng, Yuxin, Palamidessi, Catuscia, Pang, Jun
Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
We propose a probabilistic variant of the pi-calculus as a framework to specify randomized security protocols and their intended properties. In order to express and verify the correctness of the...
Separation of synchronous and asynchronous communication via testing (2007)
Cacciagrano, Diletta, Corradini, Flavio, Palamidessi, Catuscia
One of the early results about the asynchronous $\pi$-calculus which significantly contributed to its popularity is the capability of encoding the output prefix of the (choiceless) $\pi$-calculus in...
Axiomatizations for probabilistic finite-state behaviors (2007)
Deng, Yuxin, Palamidessi, Catuscia
We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's probabilistic automata. We consider various strong and weak behavioral...
Cacciagrano, Diletta, Corradini, Flavio, Palamidessi, Catuscia
In this paper, we define fair computations in the pi-calculus. We follow Costa and Stirling's approach for CCS-like languages but exploit a more natural labeling method of process actions to filter...
Making Random Choices Invisible to the Scheduler (2007)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to resolve the nondeterminism. It...
Symbolic Bisimulation for Probabilistic Systems (2007)
Wu, Peng, Palamidessi, Catuscia, Lin, Huimin
The paper introduces symbolic bisimulations for a simple probabilistic π-calculus to overcome the infinite branching problem that still exists in checking ground bisimulations between...
Model checking the probabilistic pi-calculus (2007)
Norman, Gethin, Palamidessi, Catuscia, Parker, David, Wu, Peng
We present an implementation of model checking for the probabilistic pi-calculus, a process algebra which supports modelling of concurrency, mobility and discrete probabilistic behaviour. Formal...
A Probabilistic Applied Pi-Calculus (2007)
Goubault-Larrecq, Jean, Palamidessi, Catuscia, Troina, Angelo
We propose an extension of the Applied Picalculus by introducing nondeterministic and probabilistic choice operators. The semantics of the resulting model, in which probability and nondeterminism...
Tutorial on separation results in process calculi via leader election problems (2007)
Vigliotti, Maria Grazia, Phillips, Iain, Palamidessi, Catuscia
We compare the expressive power of process calculi by studying the problem of electing a leader in a symmetric network of processes. We consider the \pi-calculus with mixed choice, separate choice...
Expressiveness of Recursion, Replication and Scope Mechanisms in Process Calculi (2007)
Aranda, Jesus, Di Giusto, Cinzia, Palamidessi, Catuscia, Valencia, Frank
In this paper we shall survey and discuss in detail the work on the relative expressiveness of recursion and replication in various process calculi. Namely, CCS, the pi-calculus, the Ambient...
Expressiveness of Recursion, Replication and Scope Mechanisms in Process Calculi (2007)
Aranda, Jesus, Di Giusto, Cinzia, Palamidessi, Catuscia, Valencia, Frank
In this paper we shall survey and discuss in detail the work on the relative expressiveness of recursion and replication in various process calculi. Namely, CCS, the pi-calculus, the Ambient...
Probability of Error in Information-Hiding Protocols (2007)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
Randomized protocols for hiding private information can fruitfully be regarded as noisy channels in the information-theoretic sense, and the inference of the concealed information can be regarded as...
Declarative Diagnosis of Temporal Concurrent Constraint Programs (2007)
Falaschi, Moreno, Olarte, Carlos, Palamidessi, Catuscia, Valencia, Frank
We present a framework for the declarative diagnosis of nondeterministic timed concurrent constraint programs. We present a denotational semantics based on a (continuous) immediate consequence...
Weak Probabilistic Anonymity (2007)
Deng, Yuxin, Palamidessi, Catuscia, Pang, Jun
Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
We propose a probabilistic variant of the pi-calculus as a framework to specify randomized security protocols and their intended properties. In order to express and verify the correctness of the...
Separation of synchronous and asynchronous communication via testing (2007)
Cacciagrano, Diletta, Corradini, Flavio, Palamidessi, Catuscia
One of the early results about the asynchronous $\pi$-calculus which significantly contributed to its popularity is the capability of encoding the output prefix of the (choiceless) $\pi$-calculus in...
Axiomatizations for probabilistic finite-state behaviors (2007)
Deng, Yuxin, Palamidessi, Catuscia
We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's probabilistic automata. We consider various strong and weak behavioral...
Cacciagrano, Diletta, Corradini, Flavio, Palamidessi, Catuscia
In this paper, we define fair computations in the pi-calculus. We follow Costa and Stirling's approach for CCS-like languages but exploit a more natural labeling method of process actions to filter...
Making Random Choices Invisible to the Scheduler (2007)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to resolve the nondeterminism. It...
Symbolic Bisimulation for Probabilistic Systems (2007)
Wu, Peng, Palamidessi, Catuscia, Lin, Huimin
The paper introduces symbolic bisimulations for a simple probabilistic π-calculus to overcome the infinite branching problem that still exists in checking ground bisimulations between...
Model checking the probabilistic pi-calculus (2007)
Norman, Gethin, Palamidessi, Catuscia, Parker, David, Wu, Peng
We present an implementation of model checking for the probabilistic pi-calculus, a process algebra which supports modelling of concurrency, mobility and discrete probabilistic behaviour. Formal...
A Probabilistic Applied Pi-Calculus (2007)
Goubault-Larrecq, Jean, Palamidessi, Catuscia, Troina, Angelo
We propose an extension of the Applied Picalculus by introducing nondeterministic and probabilistic choice operators. The semantics of the resulting model, in which probability and nondeterminism...
Tutorial on separation results in process calculi via leader election problems (2007)
Vigliotti, Maria Grazia, Phillips, Iain, Palamidessi, Catuscia
We compare the expressive power of process calculi by studying the problem of electing a leader in a symmetric network of processes. We consider the \pi-calculus with mixed choice, separate choice...
Model checking the probabilistic π-calculus (2007)
Gethin Norman, Catuscia Palamidessi, David Parker, Peng Wu
We present an implementation of model checking for the probabilistic π-calculus, a process algebra which supports modelling of concurrency, mobility and discrete probabilistic behaviour. Formal...
Making random choices invisible to the scheduler (2007)
Konstantinos Chatzikokolakis, Catuscia Palamidessi
Abstract. When dealing with process calculi and automata which express both nondeterministic and probabilistic behavior, it is customary to introduce the notion of scheduler to resolve the...
Probability of error in information-hiding protocols (2007)
Konstantinos Chatzikokolakis, Catuscia Palamidessi
Randomized protocols for hiding private information can often be regarded as noisy channels in the informationtheoretic sense, and the inference of the concealed information can be regarded as a...
A Declarative Framework for Security: Secure Concurrent Constraint Programming (2006)
López, Hugo A., Palamidessi, Catuscia, Pérez, Jorge Andrés, Rueda, Camilo, Valencia, Frank
Due to technological advances such as the Internet and mobile computing, Security has become a serious challenge involving several disciplines of Computer Science. In recent years, there has been a...
A Declarative Framework for Security: Secure Concurrent Constraint Programming (2006)
López, Hugo A., Palamidessi, Catuscia, Pérez, Jorge Andrés, Rueda, Camilo, Valencia, Frank
Due to technological advances such as the Internet and mobile computing, Security has become a serious challenge involving several disciplines of Computer Science. In recent years, there has been a...
Probable Innocence Revisited (2006)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
Often we wish to ensure that the identity of the user performing a certain action is maintained secret. This property is called anonymity. Examples of situations in which we may wish to provide...
Languages for Concurrency (2006)
Palamidessi, Catuscia, Valencia, Frank
This essay offers an overview of basic aspects and central development in Concurrency Theory based on formal languages. In particular, it focuses on the theory of Process Calculi.
A Congruence Format for Name-passing Calculi (2006)
Ziegler, Axelle, Miller, Dale, Palamidessi, Catuscia
We define and use a SOS-based framework to specify the transition systems of calculi with name-passing properties. This setting uses proof-theoretic tools to take care of some of the difficulties...
Metrics for Action-labelled Quantitative Transition Systems (2006)
Deng, Yuxin, Chothia, Tom, Palamidessi, Catuscia, Pang, Jun
This paper defines action-labelled quantitative transition systems as a general framework for combining qualitative and quantitative analysis. We define state-metrics as a natural extension of...
Expressiveness of probabilistic \pi-calculi (2006)
Pradalier, Sylvain, Palamidessi, Catuscia
In this work we propose a probabilistic extension of the -calculus. The main novelty is a probabilistic mixed choice operator, that is, a choice construct with a probability distribution on the...
On the Expressiveness of Linearity vs Persistence in the Asychronous Pi-Calculus (2006)
Palamidessi, Catuscia, Saraswat, Vijay, Valencia, Frank, Victor, Bjorn
We present an expressiveness study of linearity and persistence of processes. We choose the pi-calculus, one of the main representatives of process calculi, as a framework to conduct our study. We...
Probabilistic and nondeterministic aspects of Anonymity (2006)
Anonymity means that the identity of the user performing a certain action is main- tained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Probable Innocence Revisited (2006)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
In this paper we propose a formalization of probable innocence, a notion of probabilistic anonymity that is associated to realistic protocols such as Crowds. We analyze critically two different...
Anonymity Protocols as Noisy Channels (2006)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
We consider a framework in which anonymity protocols are interpreted as noisy channels in the information-theoretic sense, and we explore the idea of using the notion of capacity as a measure of the...
Expressiveness via Leader Election Problems (2006)
Vigliotti, Maria Grazia, Phillips, Iain, Palamidessi, Catuscia
We compare the expressive power of process calculi by studying the problem of electing a leader in a symmetric network of processes. We consider the π-calculus with mixed choice and with...
Probable Innocence Revisited (2006)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
Often we wish to ensure that the identity of the user performing a certain action is maintained secret. This property is called anonymity. Examples of situations in which we may wish to provide...
Languages for Concurrency (2006)
Palamidessi, Catuscia, Valencia, Frank
This essay offers an overview of basic aspects and central development in Concurrency Theory based on formal languages. In particular, it focuses on the theory of Process Calculi.
A Congruence Format for Name-passing Calculi (2006)
Ziegler, Axelle, Miller, Dale, Palamidessi, Catuscia
We define and use a SOS-based framework to specify the transition systems of calculi with name-passing properties. This setting uses proof-theoretic tools to take care of some of the difficulties...
Metrics for Action-labelled Quantitative Transition Systems (2006)
Deng, Yuxin, Chothia, Tom, Palamidessi, Catuscia, Pang, Jun
This paper defines action-labelled quantitative transition systems as a general framework for combining qualitative and quantitative analysis. We define state-metrics as a natural extension of...
Expressiveness of probabilistic \pi-calculi (2006)
Pradalier, Sylvain, Palamidessi, Catuscia
In this work we propose a probabilistic extension of the -calculus. The main novelty is a probabilistic mixed choice operator, that is, a choice construct with a probability distribution on the...
On the Expressiveness of Linearity vs Persistence in the Asychronous Pi-Calculus (2006)
Palamidessi, Catuscia, Saraswat, Vijay, Valencia, Frank, Victor, Bjorn
We present an expressiveness study of linearity and persistence of processes. We choose the pi-calculus, one of the main representatives of process calculi, as a framework to conduct our study. We...
Probabilistic and nondeterministic aspects of Anonymity (2006)
Anonymity means that the identity of the user performing a certain action is main- tained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Probable Innocence Revisited (2006)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
In this paper we propose a formalization of probable innocence, a notion of probabilistic anonymity that is associated to realistic protocols such as Crowds. We analyze critically two different...
Anonymity Protocols as Noisy Channels (2006)
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia, Panangaden, Prakash
We consider a framework in which anonymity protocols are interpreted as noisy channels in the information-theoretic sense, and we explore the idea of using the notion of capacity as a measure of the...
Expressiveness via Leader Election Problems (2006)
Vigliotti, Maria Grazia, Phillips, Iain, Palamidessi, Catuscia
We compare the expressive power of process calculi by studying the problem of electing a leader in a symmetric network of processes. We consider the π-calculus with mixed choice and with...
On the expressiveness of linearity vs persistence in the asychronous pi-calculus (2006)
Catuscia Palamidessi, Frank D. Valencia
We present an expressiveness study of linearity and persistence of processes. We choose the π-calculus, one of the main representatives of process calculi, as a framework to conduct our study. We...
Konstantinos Chatzikokolakis, Catuscia Palamidessi
Abstract. We propose a probabilistic variant of the pi-calculus as a framework to specify randomized security protocols and their intended properties. In order to express an verify the correctness of...
Anonymity protocols as noisy channels (2006)
Konstantinos Chatzikokolakis, Catuscia Palamidessi, Prakash Panangaden
Abstract. We propose a framework in which anonymity protocols are interpreted as particular kinds of channels, and the degree of anonymity provided by the protocol as the converse of the channel’s...
A Framework for Analyzing Probabilistic (2006)
Protocols And Its, Konstantinos Chatzikokolakis, Catuscia Palamidessi
We propose a probabilistic variant of the pi-calculus as a framework to specify randomized security protocols and their intended properties. In order to express an verify the correctness of the...
Probabilistic Anonymity (2006)
Palamidessi, Catuscia, Bhargava, Mohit
The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending mails. A formal definition of this...
Roberto Amadio, Diletta Cacciagrano, Flavio Corradini, Catuscia Palamidessi
v Hagen Völzer (Express Invited Speaker)
Recursion vs Replication in Process Calculi: Expressiveness (2005)
Palamidessi, Catuscia, Valencia, Frank
In this paper we shall survey and discuss in detail the work on the relative expressiveness of recursion and replication in various process calculi. Namely, CCS, the pi-calculus, and the Ambient...
Recursion vs Replication in Process Calculi: Expressiveness (2005)
Palamidessi, Catuscia, Valencia, Frank
In this paper we shall survey and discuss in detail the work on the relative expressiveness of recursion and replication in various process calculi. Namely, CCS, the pi-calculus, and the Ambient...
Compositional Reasoning for Probabilistic Finite-State Behaviors (2005)
Deng, Yuxin, Palamidessi, Catuscia, Pang, Jun
We study a process algebra which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's simple probabilistic automata. We consider strong bisimulation and...
Probabilistic Anonymity (2005)
Bhargava, Mohit, Palamidessi, Catuscia
The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending mails. The systems for ensuring...
A randomized encoding of the pi-calculus with mixed choice (2005)
Palamidessi, Catuscia, Herescu, Oltea Mihaela
We consider the problem of encoding the pi-calculus with mixed choice into the asynchronous pi-calculus via a uniform translation while preserving a reasonable semantics. Although it has been shown...
Separation of synchronous and asynchronous communication via testing (2005)
Cacciagrano, Diletta, Corradini, Flavio, Palamidessi, Catuscia
One of the early results about the asynchronous pi-calculus which significantly contributed to its popularity is the capability of encoding the output prefix of the (choiceless) pi-calculus in a...
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
We propose a probabilistic variant of the pi-calculus as a framework to specify randomized security protocols and their intended properties. In order to express an verify the correctness of the...
Axiomatizations for probabilistic finite-state behaviors (2005)
Deng, Yuxin, Palamidessi, Catuscia
We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's probabilistic automata. We consider various strong and weak behavioral...
Compositional Reasoning for Probabilistic Finite-State Behaviors (2005)
Deng, Yuxin, Palamidessi, Catuscia, Pang, Jun
We study a process algebra which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's simple probabilistic automata. We consider strong bisimulation and...
Probabilistic Anonymity (2005)
Bhargava, Mohit, Palamidessi, Catuscia
The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending mails. The systems for ensuring...
A randomized encoding of the pi-calculus with mixed choice (2005)
Palamidessi, Catuscia, Herescu, Oltea Mihaela
We consider the problem of encoding the pi-calculus with mixed choice into the asynchronous pi-calculus via a uniform translation while preserving a reasonable semantics. Although it has been shown...
Separation of synchronous and asynchronous communication via testing (2005)
Cacciagrano, Diletta, Corradini, Flavio, Palamidessi, Catuscia
One of the early results about the asynchronous pi-calculus which significantly contributed to its popularity is the capability of encoding the output prefix of the (choiceless) pi-calculus in a...
Chatzikokolakis, Konstantinos, Palamidessi, Catuscia
We propose a probabilistic variant of the pi-calculus as a framework to specify randomized security protocols and their intended properties. In order to express an verify the correctness of the...
Axiomatizations for probabilistic finite-state behaviors (2005)
Deng, Yuxin, Palamidessi, Catuscia
We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's probabilistic automata. We consider various strong and weak behavioral...
Compositional reasoning for probabilistic finite-state behaviors (2005)
Yuxin Deng, Catuscia Palamidessi, Jun Pang
Abstract. We study a process algebra which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch’s simple probabilistic automata. We consider strong...
Weak probabilistic anonymity (2005)
Yuxin Deng, Catuscia Palamidessi, Jun Pang, Inria Sophia-antipolis, Inria Futurs, ...
Abstract. Anonymity means that the identity of the user performing a certain action is maintained secret. The protocols for ensuring anonymity often use random mechanisms which can be described...
Compositional reasoning for probabilistic finite-state behaviors (2005)
Yuxin Deng, Catuscia Palamidessi, Jun Pang
Abstract. We study a process algebra which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's simple probabilistic automata. We consider strong...
Axiomatizations for probabilistic finite-state behaviors (2005)
Yuxin Deng, Catuscia Palamidessi
Abstract. We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's probabilistic automata. We consider various strong and...
Axiomatizations for probabilistic finite-state behaviors (2005)
Yuxin Deng, Catuscia Palamidessi, Inria Sophia-antipolis, Inria Futurs, Ecole Polytechnique
Abstract. We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's probabilistic automata. We consider various strong and...
Recursion vs replication in process calculi: Expressiveness (2005)
Catuscia Palamidessi, Inria Futurs, École Polytechnique, Frank D. Valencia
Metrics for Action-labelled Quantitative Transition Systems (2005)
Yuxin Deng, Tom Chothia, Catuscia Palamidessi, Jun Pang
This paper defines action-labelled quantitative transition systems as a general framework for combining qualitative and quantitative analysis. We define state-metrics as a natural extension of...
Metrics for Action-labelled Quantitative Transition Systems (2005)
Yuxin Deng, Tom Chothia, Catuscia Palamidessi, Jun Pang
This paper defines action-labelled quantitative transition systems as a general framework for combining qualitative and quantitative analysis. We define state-metrics as a natural extension of...
Compositional Reasoning for Probabilistic Finite-State Behaviors (2005)
Yuxin Deng, Catuscia Palamidessi, Jun Pang
We study a process algebra which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch's simple probabilistic automata. We consider strong bisimulation and...
Axiomatizations for probabilistic finite-state behaviors (2005)
Yuxin Deng, Catuscia Palamidessi, Inria Sophia-antipolis, Inria Futurs, École Polytechnique
Abstract. We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch’s probabilistic automata. We consider various strong and weak...
Compositional reasoning for probabilistic finite-state behaviors (2005)
Yuxin Deng, Catuscia Palamidessi, Jun Pang
Abstract. We study a process algebra which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch’s simple probabilistic automata. We consider strong...
Weak probabilistic anonymity (2005)
Mohit Bhargava, Catuscia Palamidessi
Abstract. The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending mails. The systems for...
Separation Results Via Leader Election Problems. FMCO 2005 (2005)
Maria Grazia Vigliotti, Iain Phillips, Catuscia Palamidessi
Abstract. We compare the expressive power of process calculi by studying the problem of electing a leader in a symmetric network of processes. We consider the π-calculus with mixed choice and with...
Axiomatizations for probabilistic finite-state behaviors (2005)
Yuxin Deng, Catuscia Palamidessi
Abstract. We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch’s probabilistic automata. We consider various strong and weak...
Polynomial Time Preemptive Sum-Multicoloring on Paths (2005)
Kovacs, Annamaria, Caires, Luis, Italiano, Giuseppe F., Monteiro, Luís, Palamidessi, Catuscia, Yung, Moti
Approximation algorithms for Euclidean Group TSP (2005)
Elbassioni, Khaled, Fishkin, Aleksei, Mustafa, Nabil H., Sitters, Rene, Caires, Luis, Italiano, Giuseppe F., ...
Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus (2003)
The Asynchronous $\pi$-calculus, proposed by Honda and Tokoro (1991) and, independently, by Boudol (1992), is a subset of the $\pi$-calculus \cite{Milner:92:IC} which contains no explicit operators...
Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus (2003)
The Asynchronous $\pi$-calculus, proposed by Honda and Tokoro (1991) and, independently, by Boudol (1992), is a subset of the $\pi$-calculus \cite{Milner:92:IC} which contains no explicit operators...
On the expressive power of temporal concurrent constraint programming languages (2002)
Mogens Nielsen, Catuscia Palamidessi, Frank D. Valencia
The tcc paradigm is a formalism for timed concurrent constraint programming. Several tcc languages di#ering in their way of expressing infinite behavior have been proposed in the literature. In this...
On the expressive power of concurrent constraint programming languages (2002)
Mogens Nielsen, Catuscia Palamidessi, Frank D. Valencia, Frank D. Valencia
et al.:
A Randomized Distributed Encoding of the π-Calculus with Mixed Choice (2002)
Catuscia Palamidessi, Oltea Mihaela Herescu
We consider the problem of encoding the -calculus (more precisely, the version of the -calculus with mixed choice) into the asynchronous -calculus via a uniform translation preserving a reasonable...
Mogens Nielsen, Catuscia Palamidessi, Frank D. Valencia, Copyright C, Mogens Nielsen, Catuscia Palamidessi, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Temporal Concurrent Constraint Programming: Denotation, Logic And Applications (2002)
Mogens Nielsen, Catuscia Palamidessi, Frank D. Valencia
The tcc model is a formalism for reactive concurrent constraint programming. We present a model of temporal concurrent constraint programming which adds to tcc the capability of modeling asynchronous...
Probabilistic asynchronous pi-calculus (2001)
Herescu, Oltea Mihaela, Palamidessi, Catuscia
We propose an extension of the asynchronous pi-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by the...
On the generalized dining philosophers problem (2001)
Herescu, Oltea Mihaela, Palamidessi, Catuscia
We consider a generalization of the dining philosophers problem to arbitrary connection topologies. We focus on symmetric, fully distributed systems, and we address the problem of guaranteeing...
Pint : a Java interpreter for the [pi]-calculus / (2001)
Daigle, Shawna L., Palamidessi, Catuscia.
Thesis supervisor: Catuscia Palamidessi.
A Temporal Concurrent Constraint Programming Calculus (2001)
Palamidessi Valencia, Catuscia Palamidessi, Catuscia Palamidessi, Catuscia Palamidessi, Frank D. Valencia, Frank D. Valencia, ...
The tcc model is a formalism for reactive concurrent constraint programming. In this paper we propose a model of temporal concurrent constraint programming which adds to tcc the capability of...
A Randomized Encoding of the π-Calculus with Mixed Choice (2001)
Catuscia Palamidessi, Oltea Mihaela Herescu
We consider the problem of encoding the -calculus with mixed choice into the asynchronous -calculus via a uniform translation while preserving a reasonable semantics. Although it has been shown that...
The Replacement Operation for CCP Programs (2000)
Bertolino, Marco, Etalle, Sandro, Palamidessi, Catuscia
The Replacement is a very powerful transformation operation which - both within the functional paradigm as well as within the logic programming one - can micic the most common transformation...
Probabilistic asynchronous -calculus (2000)
Oltea Mihaela Herescu, Catuscia Palamidessi
Abstract. We propose an extension of the asynchronous-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by...
Concurrent constraint programming with process mobility (2000)
David Gilbert, Catuscia Palamidessi
Abstract. We propose an extension of concurrent constraint programming with primitives for process migration within a hierarchical network, and we study its semantics. To this purpose, we first...
Probabilistic asynchronous -calculus (2000)
Oltea Mihaela Herescu, Catuscia Palamidessi
Abstract. We propose an extension of the asynchronous-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by...
Probabilistic asynchronous -calculus (2000)
Oltea Mihaela Herescu, Catuscia Palamidessi
We propose an extension of the asynchronous #-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by the...
The Replacement Operation for CCP Programs (2000)
Marco Bertolino, Sandro Etalle, Catuscia Palamidessi
. The replacement is a very powerful transformation operation which { both within the functional paradigm as well as within the logic programming one { can mimic the most common transformation...
Concurrent Constraint Programming with Process Mobility (2000)
David Gilbert, Catuscia Palamidessi
. We propose an extension of concurrent constraint programming with primitives for process migration within a hierarchical network, and we study its semantics. To this purpose, we first investigate a...
The Replacement Operation for CCP Programs (1999)
Bertolino, Marco, Etalle, Sandro, Palamidessi, Catuscia
The Replacement is a very powerful transformation operation which - both within the functional paradigm as well as within the logic programming one - can micic the most common transformation...
C. Palamdessi, Catuscia Palamidessi
A fully abstract model for concurrent constraint programming
Foundational Aspects of Syntax (1999)
Dale Miller, Catuscia Palamidessi
Introduction A large variety of computing systems, such as compilers, interpreters, static analyzers, and theorem provers, need to manipulate syntactic objects like programs, types, formulas, and...
Foundational Aspects of Syntax (1999)
Dale Miller And, Dale Miller, Catuscia Palamidessi
Introduction A large variety of computing systems, such as compilers, interpreters, static analyzers, and theorem provers, need to manipulate syntactic objects like programs, types, formulas, and...
Comparing the expressive power of the Synchronous and the Asynchronous pi-calculus (1998)
The Asynchronous pi-calculus, as recently proposed by Boudol and, independently, by Honda and Tokoro, is a subset of the pi-calculus which contains no explicit operators for choice and...
Encoding Transition Systems in Sequent Calculus (1997)
Raymond Mcdowell, Dale Miller, Catuscia Palamidessi
Linear logic has been used to specify the operational semantics of various process calculi. In this paper we explore how meta-level judgments, such as simulation and bisimulation, can be established...
Comparing the Expressive Power of the Synchronous and the Asynchronous pi-calculus (1997)
The Asynchronous ß-calculus, as recently proposed by Boudol and, independently, by Honda and Tokoro, is a subset of the ß-calculus which contains no explicit operators for choice and...
An Algebraic Perspective of Constraint Logic Programming (1997)
De BOER, FRANK S., Di PIERRO, ALESSANDRA, PALAMIDESSI, CATUSCIA
We develop a denotational, fully abstract semantics for constraint logic programming (clp) with respect to successful and failed observables. The denotational approach turns out very useful for the...
Encoding Transition Systems in Sequent Calculus (1996)
Raymond Mcdowell, Dale Miller, Catuscia Palamidessi
Intuitionistic and linear logics can be used to specify the operational semantics of transition systems in various ways. We consider here two encodings: one uses linear logic and maps states of the...
Weak relative pseudo-complements of closure operators (1996)
Roberto Giacobazzi, Catuscia Palamidessi, Francesco Ranzato
We define the notion of weak relative pseudo-complement on meet semi-lattices, and we show that it is strictly weaker than relative pseudo-complementation, but stronger than pseudo-complementation....
Encoding Transition Systems in Sequent Calculus (1996)
Raymond Mcdowell, Dale Miller, Catuscia Palamidessi
Intuitionistic and linear logics can be used to specify the operational semantics of transition systems in various ways. We consider here two encodings: one uses linear logic and maps states of the...
Confluence in Concurrent Constraint Programming (1996)
Moreno Falaschi, Maurizio Gabbrielli, K. Marriott, C. Palamidessi, Moreno Falaschi, Maurizio Gabbrielli, ...
Concurrent constraint programming (ccp), like most of the concurrent paradigms, has a mechanism of global choice which makes computations dependent on the scheduling of processes. This is one of the...
Encoding Transition Systems in Sequent Calculus: Preliminary Report (1996)
Raymond Mcdowell, Dale Miller, Catuscia Palamidessi
Linear logic has been used to specify the operational semantics of various process calculi. In this paper we explore how meta-level judgments, such as simulation and bisimulation, can be established...
Encoding Transition Systems in Sequent Calculus: Preliminary Report (1996)
Raymond Mcdowell, Dale Miller, Catuscia Palamidessi
Linear logic has been used to specify the operational semantics of various process calculi. In this paper we explore how meta-level judgments, such as simulation and bisimulation, can be established...
Linear Constraint Systems as High-level Nets (1996)
Eike Best, Catuscia Palamidessi
Linear constraint systems are simple deductive systems based on the main underlying idea of linear logic: hypotheses represent physical resources which are consumed by the entailment relation. For...
Encoding Transition Systems in Sequent Calculus: Preliminary Report (1996)
Raymond Mcdowell, Dale Miller, Catuscia Palamidessi
Linear logic has been used to specify the operational semantics of various process calculi. In this paper we explore how meta-level judgments, such as simulation and bisimulation, can be established...
Constraint Logic Programming with Dynamic Scheduling: A Semantics Based on Closure Operators (1996)
Moreno Falaschi, Maurizio Gabbrielli, Kim Marriott, Catuscia Palamidessi
The first logic programming languages, such as Prolog, used a fixed left-to-right atom scheduling rule. Recent logic programming languages, however, provide more flexible scheduling in which there is...
Algebraic Properties of Idempotent Substitutions (1996)
This paper presents an algebra of idempotent substitutions whose operations have many properties. We provide an algorithm to compute these operations and we show how they are related to the standard...
Weak Relative Pseudo-Complements of Closure Operators (1996)
Roberto Giacobazzi, Catuscia Palamidessi, Francesco Ranzato
We define the notion of weak relative pseudo-complement, and we show that, for an arbitrary lattice, the property of weak relative pseudo-complementation is strictly weaker than relative...
Palamidessi: Linear constraint systems as high-level nets (1996)
Eike Best, Catuscia Palamidessi
Abstract. Linear constraint systems are simple deductive systems based on the main underlying idea of linear logic: hypotheses represent physical resources which are consumed by the entailment...
An algebraic perspective of constraint logic programming (1995)
Ra Di Pierro, Catuscia Palamidessi
programming
Weak Relative Pseudo-Complements of Closure Operators (1995)
Roberto Giacobazzi, Roberto Giacobazzi, Catuscia Palamidessi, Catuscia Palamidessi, Francesco Ranzato, Francesco Ranzato
We define the notion of weak relative pseudo-complement, and we show that, for an arbitrary lattice, the property of weak relative pseudo-complementation is strictly weaker than relative...
Confluence in Concurrent Constraint Programming (1995)
Moreno Falaschi, Maurizio Gabbrielli, Kim Marriott, Catuscia Palamidessi
Concurrent constraint programming (ccp), like most of the concurrent paradigms, has a mechanism of global choice which makes computations dependent on the scheduling of processes. This is one of the...
Proving Concurrent Constraint Programs Correct (1994)
Frank De, Maurizio Gabbrielli, Elena Marchiori, Catuscia Palamidessi
We develop a compositional proof-system for the partial correctness of concurrent constraint programs. Soundness and (relative) completeness of the system are proved with respect to a denotational...
Proving Concurrent Constraint Programs Correct (1994)
Frank De, Maurizio Gabbrielli, Elena Marchiori, Catuscia Palamidessi
We develop a compositional proof-system for the partial correctness of concurrent constraint programs. Soundness and (relative) completeness of the system are proved with respect to a denotational...
Embedding as a tool for Language Comparison (1994)
Catuscia Palamidessi, Catuscia Palamidessi
This paper addresses the problem of defining a formal tool to compare the expressive power of different concurrent constraint languages. We refine the notion of embedding by adding some...
Compositional Analysis for Concurrent Constraint Programming (1993)
Moreno Falaschi, Maurizio Gabbrielli, Kim Marriott, Catuscia Palamidessi
We propose a framework for the analysis of concurrent constraint programming (ccp). Our approach is based on simple denotational semantics which approximate the usual semantics in the sense that they...
From Concurrent Logic Programming to Concurrent Constraint (1993)
The endeavor to extend logic programming to a language suitable for concurrent systems has stimulated in the last decade an intensive research, resulting in a large variety of proposals. A common...
Joost N. Kok, Catuscia Palamidessi
We develop a general semantic theory of asynchronous communication in concurrent logic and concurrent constraint languages. The main characteristic of these languages, from the point of view of the...
A theory of first-order built-in's of Prolog (1992)
K. R. Apt, E. Marchiori, C. Palamidessi, Krzysztof R. Apt, Elena Marchiori, Catuscia Palamidessi
We provide here a framework for studying Prolog programs with various built-in's that include arithmetic operations, and such metalogical relations like var and ground. To this end we propose a...
Structural Operational Semantics for AKL (1992)
Seif Haridi, Sverker Janson, Catuscia Palamidessi
The Andorra Kernel Language (AKL) is a concurrent constraint programming language. It can be seen as a general combination of logic programming languages such as Prolog, GHC, and Parlog, the first of...
A Declarative Approach for First-Order Built-in's of Prolog (1992)
Krzysztof R. Apt, Elena Marchiori, Catuscia Palamidessi
We provide here a framework for studying Prolog programs with various built-in's that include arithmetic operations, and such metalogical relations like var and ground. To this end we propose a...