G. Ramalingam

I was a graduate student at the Computer Sciences Department of the University of Wisconsin - Madison from 1987 to 1993, where I completed my Ph.D. under the guidance of Prof. Thomas Reps. From 1993 to 2006 July, I was with the IBM T.J.Watson Research Center. I am now with Microsoft Research India in Bangalore, India. You can reach me at: grama at microsoft dot com or at: gramalingam dot acm dot org.

Publications

ACM mandated notice: The documents distributed by this server have been provided by the contributing author(s) as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Note: Links designated [ACM] indicate papers available from the ACM Digital Library and access to these papers may require a registration/subscription to the ACM Digital Library.

Effective Typestate Verification in the Presence of Aliasing

S. J. Fink, E. Yahav, N. Dor, G. Ramalingam, and E. Geay
In International Symposium on Software Testing and Analysis, July 2006.
PDF

Semantics-based Reverse Engineering of Object-Oriented Data Models

G. Ramalingam, R. Komondoor, J. Field, and S. Sinha
In 28th International Conference on Software Engineering, May 2006.
PDF

Dependent Types for Program Understanding

R. Komondoor, G. Ramalingam, S. Chandra, and J. Field
In Eleventh International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Apr 2005.
PDF

Predicate abstraction and canonical abstraction for singly-linked lists

R. Manevich, E. Yahav, G. Ramalingam, and M. Sagiv.
In Sixth International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2005), Jan 2005.
PDF

Partially disjunctive heap abstraction

R. Manevich, M. Sagiv, G. Ramalingam, and J. Field.
In Eleventh International Static Analysis Symposium August 2004.
PDF Postscript

Verifying safety properties using separation and heterogeneous abstraction

Eran Yahav and G. Ramalingam.
In Proceedings of the SIGPLAN '04 Conference on Programming Language Design and Implementation, pages 25--34, 2004.
PDF Postscript

Typestate verification: Abstraction techniques and complexity results

J. Field, D. Goyal, G. Ramalingam, and E. Yahav.
In Science of Computer Programming, Volume 58, Issues 1--2, pages 57--82, October 2005.
PDF
An earlier version appeared in Tenth International Static Analysis Symposium, volume 2694 of Lecture Notes in Computer Science, pages 439--462. Springer-Verlag, June 2003.
PDF Postscript

Compactly representing first-order structures for static analysis

R. Manevich, G. Ramalingam, J. Field, D. Goyal, and M. Sagiv.
In Ninth International Static Analysis Symposium, volume 2477 of Lecture Notes in Computer Science, pages 196--212. Springer-Verlag, 2002.
PDF

On loops, dominators, and dominance frontiers

G. Ramalingam.
ACM Transactions on Programming Languages and Systems, 24(5):455--490, 2002.
Postscript ACM

Deriving specialized analyses for certifying component-client conformance

G. Ramalingam, A. Warshavsky, J. Field, D. Goyal, and M. Sagiv.
In Proceedings of the SIGPLAN '02 Conference on Programming Language Design and Implementation, pages 83--94, 2002.
PDF ACM

On sparse evaluation representations

G. Ramalingam.
Theoretical Computer Science, 277:119--147, 2002.
Technical Report Version (Postscript)

On loops, dominators, and dominance frontiers

G. Ramalingam.
In Proceedings of the SIGPLAN '00 Conference on Programming Language Design and Implementation, pages 233--241, 2000.
Postscript Extended Journal Version (Postscript)

Context-sensitive synchronization-sensitive analysis is undecidable

G. Ramalingam.
ACM Transactions on Programming Languages and Systems, 22(2):416--430, 2000.
Technical Report Version (Postscript)

Identifying loops in almost linear time

G. Ramalingam.
ACM Transactions on Programming Languages and Systems, 21(2):175--188, 1999.
Postscript ACM

Identifying procedural structure in cobol programs

John Field and G. Ramalingam.
In Workshop on Program Analysis For Software Tools and Engineering, pages 1--10, 1999.
Postscript

Solving systems of difference constraints incrementally

G. Ramalingam, J. Song, L. Joskowicz, and R. E. Miller.
Algorithmica, 23(3):261--275, 1999.
Earlier Technical Report (Postscript)

Aggregate structure identification and its application to program analysis

G. Ramalingam, John Field, and Frank Tip.
In Conference Record of the 26th ACM Symposium on Principles of Programming Languages, pages 119--132, 1999.
Postscript

On sparse evaluation representations

G. Ramalingam.
In Fourth International Static Analysis Symposium, volume 1302 of Lecture Notes in Computer Science, pages 1--15. Springer-Verlag, 1997.
Extended Technical Report (Postscript)

A member lookup algorithm for {C}++

G. Ramalingam and Harini Srinivasan.
In Proceedings of the SIGPLAN '97 Conference on Programming Language Design and Implementation, pages 18--30, 1997.
Postscript

Slicing class hierarchies in {C}++

F. Tip, J.D. Choi, J. Field, and G. Ramalingam.
In Proceedings of OOPSLA '96 Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 179--197, 1996.
ACM

An incremental algorithm for a generalization of the shortest-path problem

G. Ramalingam and Thomas W. Reps.
J. Algorithms, 21(2):267--305, 1996.
Postscript

On the computational complexity of dynamic graphs problems

G. Ramalingam and T. Reps.
Theoretical Computer Science, 158:233--277, 1996.

Data flow frequency analysis

G. Ramalingam.
In Proceedings of the SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 267--277, 1996.
Postscript

Parametric program slicing

John Field, G. Ramalingam, and Frank Tip.
In Conference Record of the 22nd ACM Symposium on Principles of Programming Languages, pages 379--392, 1995.
ACM

The undecidability of aliasing

G. Ramalingam.
ACM Transactions on Programming Languages and Systems, 16(5):1467--1471, 1994.
ACM

An incremental algorithm for maintaining the dominator tree of a reducible flowgraph

G. Ramalingam and Thomas Reps.
In Conference Record of the 21st ACM Symposium on Principles of Programming Languages, pages 287--298, 1994.
ACM

On competitive on-line algorithms for the dynamic priority-ordering problem

G. Ramalingam and Thomas Reps.
In Information Processing Letters, 51(3):155--161, 1994.

New programs from old

G. Ramalingam and Thomas Reps.
TR-1057, Computer Sciences Department, University of Wisconsin-Madison, November 1991.

Modification algebras

G. Ramalingam and Thomas Reps.
In AMAST, 547--558, 1991.

A theory of program modifications

G. Ramalingam and Thomas Reps.
In TAPSOFT, Vol. 2, 137--152, 1991.

New sequential and parallel algorithms for interval graph recognition

G. Ramalingam and C. Pandu Rangan
In Information Processing Letters, 34(4):215--219, 1990.

Semantics of program representation graphs

G. Ramalingam and Thomas Reps.
TR-900, Computer Sciences Department, University of Wisconsin-Madison, December 1989.

A unified approach to domination problems on interval graphs

G. Ramalingam and C. Pandu Rangan
In Information Processing Letters, 27(5):271--274, 1988.

Total domination in interval graphs revisited

G. Ramalingam and C. Pandu Rangan
In Information Processing Letters, 27(1):17--21, 1988.