2018/03/08 by Sohei Ito, Ito, Sohei
Computer Science · #Advanced Software Engineering Methodologies #Distributed systems and fault tolerance #FOS: Computer and information sciences #Programming Languages (cs.PL) #Software System Performance and Reliability #cs.PL
paper · pdf · doi:10.48550/arxiv.1803.02976
30 pages
arxiv created 2018/03/08 · openalex publication_date 2018/03/08 · arxiv updated 2018/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The program dependence graph (PDG) represents data and control dependence between statements in a program. This paper presents an operational semantics of program dependence graphs. Since PDGs exclude artificial order of statements that resides in sequential programs, executions of PDGs are not unique. However, we identified a class of PDGs that have unique final states of executions, called deterministic PDGs. We prove that the operational semantics of control flow graphs is equivalent to that of deterministic PDGs. The class of deterministic PDGs properly include PDGs obtained from well-structured programs. Thus, our operational semantics of PDGs is more general than that of PDGs for well-structured programs, which are already established in literature.