Total views : 210

A New Approach for Optimization of Program Dependence Graph using Finite Automata


  • BITs-Ranchi (Noida Campus), Noida - 201301, Uttar Pradesh, India


The Objective is to optimize the time in identification of similar code segment in a program, which is represented using PDG. The method adapted is minimization of finite automata, the states, which are having similar transitions, can be combined into a single state, through which we can remove the duplicate code in program. Methodology used in current study is detection of isomorphic sub graphs in a graph where the program segment has been represented using graph, this approach is very lengthy because finding of sub graphs and identifying isomorphicity between sub graphs. Findings are the demonstrated through an example in figure 1 to figure 4. The efficiency of suggested idea has been demonstrated in analysis part. This approach can be used in compiler optimization phase because it connects computationally related parts of a program; PDG is non-linear data structure in which the transformations can be performed uniformly for both data and control dependences.


DFA, Finite Automata, Isomorphic Graphs, Minimization of Finite Automata, Optimized PDG, PDG.

Full Text:

 |  (PDF views: 233)


  • Horwitz SB, Reps TW. The use of program dependence graphs in software engineering. In Proceedings of the Fourteenth International Conference on Software Engineering. 1992.
  • Horwitz SB, Reps TW, Binkley D. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems. 1990; 12(1).
  • Komondoor R. Automated Duplicated-Code Detection and Procedure Extraction, PhD at the University of Wisconsin: Madison, 2003.
  • Ettinger R. Refactoring via Program Slicing and Sliding, PhD at the Oxford University Computing Laboratory: Programming Tools Group, 2006.
  • Zanardini D. The Semantics of Abstract Program Slicing, Proc. of the 8th IEEE Int Working Conf on Source Code Analysis and Manipulation. 2008. p. 89–98.
  • Cormen TH. Introduction to Algorithms. 2nd edn. MIT Press, 1998.
  • Mens T. On the Use of Graph Transformations for Model Refactoring, Generative and Transformational Techniques in Software Engineering. 2006; 219–57.
  • Martin Fowler. Refactoring Home Page. Available from:
  • Mens T, Tourwe T. A Survey of Software Refactoring. IEEE Transactions on Software Engineering. 2004; 30(2):126–39.
  • Verbaere M, Ettinger R, de Moor O. Jun GL: A Scripting Language for Refactoring, 28th International Conference on Software Engineering. 2006. p. 172–81.
  • Komondoor R, Horwitz S. Using slicing to identify duplication in source code. In Eighth International Static Analysis Symposium (SAS), 2001.
  • Horwitz S, Prins J, Reps T. Integrating noninterfering versions of programs. ACM Transactions on Programming Languages and Systems. 1989; 11(3).
  • Holub J, Stekr S. Implementation of Deterministic Finite Automata on Parallel Computers. This research has been partially supported by the Ministry of Education, Youth and Sports under research program MSM 6840770014 and the Czech Science Foundation as project 201/06 (2009): 1039.
  • Hopcroft JE, Motwani R, Ullman JD. Introduction to automata theory, languages, and computation. ACM SIGACT News. 2001; 32(1):60–5.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.