G. Ramalingam

g r a m a at m i c r o s o f t dot c o m

This page is outdated. Please look at my current web site.

I am a member of the Rigorous Software Engineering Group at Microsoft Research India.

I am broadly interested in the areas of Programming Languages and Software Engineering, in making software development easier, more enjoyable, more reliable, more productive. Some of my more specific interests include static program analysis and programming tools.

Program Committees

Publications

Note: This website is under construction. Meanwhile, copies of some of the following papers may be found at my other home page.

Thread Quantification for Concurrent Shape Analysis.

J. Berdine, T. Lev-Ami, R. Manevich, G. Ramalingam, and M. Sagiv.
To appear in Computer Aided Verification, 2008.

Heap Decomposition for Concurrent Shape Analysis.

R. Manevich, T. Lev-Ami, M. Sagiv, G. Ramalingam, and J. Berdine.
To appear in Static Analysis Symposium, 2008.

Recovering Data Models via Guarded Dependences.

R. Komondoor and G. Ramalingam.
In Working Conference on Reverse Engineeering, 2007

Parametric Process Model Inference.

S. Sinha, G. Ramalingam, and R. Komondoor.
In Working Conference on Reverse Engineering, 2007.

Abstract Counterexample-based Refinement for Powerset Domains

R. Manevich, J. Field, T. A. Henzinger, G. Ramalingam, and M. Sagiv.
In Program Analysis and Compilation, Theory and Practice: Essays Dedicated to Reinhard Wilhelm, LNCS 4444, 2007.

Shape Analysis by Graph Decomposition

R. Manevich, J. Berdine, B. Cook, G. Ramalingam, and M. Sagiv.
In TACAS'07: 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, March 2007.

Modular Shape Analysis for Dynamically Encapsulated Programs

Rinetzky N., Poetzsch-Heffter A., Ramalingam G., Sagiv M. , and Yahav E.
In ESOP '07: 16th European Symposium on Programming. March 2007.

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. Best paper award.

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.

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.

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.

Partially disjunctive heap abstraction

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

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.

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.
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.

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.

On loops, dominators, and dominance frontiers

G. Ramalingam.
ACM Transactions on Programming Languages and Systems, 24(5):455--490, 2002. 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. ACM

On sparse evaluation representations

G. Ramalingam.
Theoretical Computer Science, 277:119--147, 2002.

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.

Context-sensitive synchronization-sensitive analysis is undecidable

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

Identifying loops in almost linear time

G. Ramalingam.
ACM Transactions on Programming Languages and Systems, 21(2):175--188, 1999. 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.

Solving systems of difference constraints incrementally

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

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.

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.

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.

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.

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.

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.