The language of certain conflicts of a nondeterministic process
Malik, R. (2010). The language of certain conflicts of a nondeterministic process. (Working paper 05/2010). Hamilton, New Zealand: University of Waikato, Department of Computer Science.
Permanent Research Commons link: http://hdl.handle.net/10289/4108
The language of certain conflicts is the most general set of behaviours of a nondeterministic process, which certainly lead to a livelock or deadlock when accepted by another process running in parallel. It is of great use in model checking to detect livelocks or deadlocks in very large systems, and in process-algebra to obtain abstractions preserving livelock and deadlock. Unfortunately, the language of certain conflicts is difficult to compute and has only been approximated in previous work. This paper presents an effective algorithm to calculate the language of certain conflicts for any given nondeterministic finite-state process and discusses its properties. The algorithm is shown to be correct and of exponential complexity.
University of Waikato, Department of Computer Science