Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-11T00:26:27.019Z Has data issue: false hasContentIssue false

A domain equation for refinement of partial systems

Published online by Cambridge University Press:  05 August 2004

MICHAEL R. A. HUTH
Affiliation:
Department of Computing, Imperial College London, South Kensington campus, London SW7 2AZ, England Email: M.Huth@doc.imperial.ac.uk
RADHA JAGADEESAN
Affiliation:
School of Computer Science, Telecommunications, and Information Sciences, DePaul University, 243 S. Wabash Avenue, Chicago, Illinois 60604-2287 Email: rjagadeesan@cs.depaul.edu
DAVID A. SCHMIDT
Affiliation:
Department of Computing and Information Sciences, Kansas State University, 234 Nichols Hall, Manhattan, Kansas 66506 Email: schmidt@cis.ksu.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A reactive system can be specified by a labelled transition system, which indicates static structure, along with temporal-logic formulas, which assert dynamic behaviour. But refining the former while preserving the latter can be difficult, because:

(i) Labelled transition systems are ‘total’ – characterised up to bisimulation – meaning that no new transition structure can appear in a refinement.

(ii) Alternatively, a refinement criterion not based on bisimulation might generate a refined transition system that violates the temporal properties.

In response, Larsen and Thomson proposed modal transition systems, which are ‘partial’, and defined a refinement criterion that preserved formulas in Hennessy–Milner logic. We show that modal transition systems are, up to a saturation condition, exactly the mixed transition systems of Dams that meet a mix condition, and we extend such systems to non-flat state sets. We then solve a domain equation over the mixed powerdomain whose solution is a bifinite domain that is universal for all saturated modal transition systems and is itself fully abstract when considered as a modal transition system. We demonstrate that many frameworks of partial systems can be translated into the domain: partial Kripke structures, partial bisimulation structures, Kripke modal transition systems, and pointer-shape-analysis graphs.

Type
Paper
Copyright
2004 Cambridge University Press