Output details

Complexity of data dependence problems for program schemas with concurrency

<10> ACM Transactions on Computational Logic is is the highest ranking journal in Logic (SCImago). This paper reports results from an EPSRC project in which Danicic was the principal investigator. It considers a fundamental problem of determining when one program point depends on another. Abstracting to the program schemas level, this problem is solvable in polynomial time for a certain class of function that includes a large proportion of practical concurrent systems. Since schemas approximate the behaviour of real programs more accurately than wholly non-deterministic programs, the results have wider potential applications than previous methods.