On the Complexity of Some Verification Problems in Process Control Specifications

Many techniques in many diverse areas in computer science, such as process modelling, process programming, decision support systems and workflow systems, use concepts for the specification of process control. These typically include concepts for the specification of sequential execution, parallelism...

Full description

Saved in:
Bibliographic Details
Published in:Computer journal 1999-01, Vol.42 (5), p.349-359
Main Author: ter Hofstede, A. H. M.
Format: Article
Language:English
Subjects:
Algebra
Decomposition
Information technology
Names
Process controls
Semantics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many techniques in many diverse areas in computer science, such as process modelling, process programming, decision support systems and workflow systems, use concepts for the specification of process control. These typically include concepts for the specification of sequential execution, parallelism, synchronization and moments of choice. This paper identifies some typical verification problems in process control specifications, such as reachability, termination, freedom of deadlock and livelock, and determines their computational complexity. These results then provide computational lower bounds for any technique using these concepts for process control.
ISSN:0010-4620
1460-2067
DOI:10.1093/comjnl/42.5.349