BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY: Branching vs. Linear Time: Semantical Perspective - Moshe Vardi\,
  Rice University
DTSTART:20110106T140000Z
DTEND:20110106T150000Z
UID:TALK28470@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:The discussion of the relative merits of linear- versus branch
 ing-time frameworks goes back to early 1980s. One of the beliefs dominatin
 g this discussion has been that the linear-time framework is not expressiv
 e enough semantically\, making linear-time logics lacking in expressivenes
 s. In this talk we examine the branching-linear issue from the perpsective
  of process equivalence\, which is one of the most fundamental notions in 
 concurrency theory. Defining a notion of process equivalence essentially a
 mounts to defining semantics for processes. \nOver the last three decades 
 numerous notions of process equivalence have been proposed. Researchers in
  this area do not anymore try to identify the "right" notion of equivalenc
 e. Rather\, focus has shifted to providing taxonomic frameworks\, such as 
 "the linear-branching spectrum"\, for the many proposed notions and trying
  to determine suitability for different applications.\n\nWe revisit here t
 his issue from a fresh perspective. We postulate three principles that we 
 view as fundamental to any discussion of process equivalence. First\, we b
 orrow from research in denotational semantics and take contextual equivale
 nce as the primary notion of equivalence. This eliminates many testing sce
 narios as either too strong or too week. Second\, we require the descripti
 on of a process to specify all relevant behavioral aspects of the process.
  Finally\, we require the observable behavior of a process to be reflected
  in its input/output behavior. Under these principles\, linear-time semant
 ics emerges as the right approach. As an example\, we apply these principl
 es to the framework of transducers\, a classical notion of state-based pro
 cess that dates back to the 1950s and is well suited to reactive systems. 
 \nWe show that our principles yield a unique notion of process equivalence
 \, which is trace based\, rather than tree based.\n\n(Joint work with Sumi
 t Nain)
LOCATION:Small lecture theatre\, Microsoft Research Ltd\, 7 J J Thomson Av
 enue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR