[moca] Questions on congruences and preorders

[Pietro Braione <braione@xxxxxxxxxxxxxx>]

I have a number of rather general questions on congruences 
and preorders in process calculi. Note that these questions
reflect my incomplete understanding of the topic, so feel 
free to correct any wrong assertion you may find in this 
post. 
Process calculi aim at defining an equational theory
of processes, at the purpose of enabling the kind of 
reasoning we use in everyday algebra. This justifies the
emphasis on congruences, as we expect that by replacing
equals with equals we obtain equals, not to speak about
the fact that this property allows us to decompose equality
proofs of complex components in the proofs of their components.
However, I also find in literature definitions of preorders
as theories of unidirectional replaceability, as opposed to 
bidirectional replaceability ensured by congruences.
While speaking with people here in my department, with no 
background on process calculi, I had the impression that they 
tend to regard preorders more useful in practical 
applications than congruences. My questions are:

1- Do you agree or not with the latter opinion? Why? 
2- I feel a strong bias in literature towards the study of
congruences rather than the study of preorders. Is my 
impression right? If the answer is yes, what are the reasons 
of this bias? Are there perhaps some essential difficulties 
in defining meaningful preorders?
3- I have the impression that operational congruences, based on
bisimulation, can be paralleled by operational (monotone) preorders,
perhaps based on simulation. Am I right? If I am not, which
interesting operational preorders can be defined? Which results
on their "congruence" (monotony) properties can be stated?
4- Which introductory papers may I read about (operational) 
preorders?

Thank you very much.

Pietro Braione
PhD Student
Politecnico di Milano

 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The "models for mobility" mailing list     mailto:moca@xxxxxxxxxxxxxxx
http://www-sop.inria.fr/mimosa/personnel/Davide.Sangiorgi/moca.html