English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of deciding whether one point in a program is data dependent uponanother is fundamental to program analysis and has been widely studied. In thispaper we consider this problem at the abstraction level of program schemas inwhich computations occur in the Herbrand domain of terms and predicate symbols,which represent arbitrary predicate functions, are allowed. Given a vertex l inthe flowchart of a schema S having only equality (variable copying) assignmentsand variables v,w, we show that it is PSPACE-hard to decide whether thereexists an execution of a program defined by S in which v holds the initialvalue of w at at least one occurrence of l on the path of execution, withmembership in PSPACE holding provided there is a constant upper bound on thearity of any predicate in S. We also consider the `dual' problem in which v isrequired to hold the initial value of w at every occurrence of l, for which theanalogous results hold. Additionally, the former problem for programs withnon-deterministic branching (in effect, free schemas) in which assignments withfunctions are allowed is proved to be polynomial-time decidable provided aconstant upper bound is placed upon the number of occurrences of theconcurrency operator in the schemas being considered. This result is promisingsince many concurrent systems have a relatively small number of threads(concurrent processes), especially when compared with the number of statementsthey have.

Complexity of Data Dependence problems for Program Schemas with Concurrency