Yanhong Annie Liu

Y. Annie Liu, Associate Professor Computer Science Department, Room 1433 State University of New York at Stony Brook Stony Brook, NY 11794-4400, USA liu@cs.sunysb.edu +1 (631) 632-8463 (voice) +1 (631) 632-8334 (fax) http://www.cs.sunysb.edu/~liu Ph.D., Cornell University, 1996

[Research Interests] [Selected Publications] [Software Systems] [Research Projects] [Research Overview]
[Courses and Seminars] [Spr06: Transaction Processing | Program Design and Optimization] [Other Pointers]

Selected Publications copyright notice [a more complete list] [my ftp directory]

¶  Y. A. Liu, S. D. Stoller, N. Li, and T. Rothamel. Optimizing aggregate array computations in loops. ACM Transactions on Programming Languages and Systems (TOPLAS), 27(1):91-125, January 2005. (at ACM | pdf)     An earlier version appeared as Liu and Stoller, Loop optimization for aggregate array computations, in Proceedings of the 1998 IEEE International Conference on Computer Languages (ICCL). (at IEEE | abstract | ps.gz | ps | slides.ps.gz | slides.ps)

¶  Y. A. Liu and S. D. Stoller. Dynamic programming via static incrementalization. Higher-Order and Symbolic Computation (HOSC), 16(1-2):37-62, March-June 2003. (at Kluwer | ps.gz | ps)     An earlier version appeared in Proceedings of the 8th European Symposium on Programming (ESOP), 1999. (at Springer | abstract | ps.gz | ps | slides.ps.gz | slides.ps)

¶  Y. A. Liu and S. D. Stoller. Eliminating dead code on recursive data. Science of Computer Programming (SCP), 47(2-3):221-242, May-June 2003. (at Elsevier | ps.gz | ps)     An earlier version appeared in Proceedings of the 6th International Static Analysis Symposium (SAS), 1999. (at Springer | abstract | ps.gz | ps)

¶  Y. A. Liu and G. Gomez. Automatic accurate cost-bound analysis for high-level languages. IEEE Transactions on Computers (TC), 50(12):1295-1390, December 2001. (at IEEE | ps.gz | ps)     An earlier version appeared as Automatic accurate time-bound analysis for high-level languages, in Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), 1998. (at Springer | ps.gz | ps)

¶  Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Strengthening invariants for efficient computation. Science of Computer Programming (SCP), 41(2):139-172, October 2001. (at Elsevier | ps.gz | ps)     An earlier version appeared as Discovering auxiliary information for incremental computation, in Conference Record of the 23rd Annual ACM Symposium on Principles of Programming Languages (POPL), 1996. (at ACM | ps.gz | ps)

¶  Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Transactions on Programming Languages and Systems (TOPLAS), 20(3):546-585, May 1998. (at ACM | ps.gz | ps)     An earlier version appeared as Liu and Teitelbaum, Caching intermediate results for program improvement, in Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM), 1995. (at ACM | ps.gz | ps)

¶  Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Science of Computer Programming (SCP), 24(1):1-39, February 1995. (at Elsevier | ps.gz | ps)

Some recent technical reports:
¶  Generating optimized code from SCR specifications (RLHL-LCTES 06) (pdf)
¶  Efficient type inference for secure information flow (HRLS-PLAS 06) (pdf)
¶  Core role-based access control: efficient implementations by transformations (LWGRCZZ-PEPM 06) (pdf)
¶  Role-based access control: a corrected and simplified specification (LS-TR 05) (pdf)
¶  Improved algorithm complexities for linear temporal logic model checking of pushdown systems (HL-VMCAI 06) (pdf)
¶  The efficient implementation of tuple pattern based retrieval (RL-TR 05) (pdf)
¶  Querying complex graphs (LS-PADL 06) (pdf)
¶  Incrementalization across object abstraction (LSGRL-OOPSLA 05) (pdf)
¶  Parametric regular path queries (LRYSH-PLDI 04) (pdf | ps.gz | ps)
¶  From Datalog rules to efficient programs with time and space guarantees (LS-PPDP 03) (ps.gz | ps)
¶  Iterate, incrementalize, and implement: A systematic approach to efficiency improvement and guarantees. (Liu-ICC 03, abstract for an invited talk) (ps.gz | ps)
¶  Optimizing Ackermann's function by incrementalization (LS-PEPM 03) (ps.gz | ps)
¶  Optimized live heap bound analysis (USL-VMCAI 03) (ps.gz | ps)
¶  A systematic incrementalization technique and its application to hardware design (JLZ-STTT 03) (ps.gz | ps)
¶  Solving regular path queries (LY-MPC 02) (ps.gz | ps)
¶  Program optimization using indexed and recursive data structures (LS-PEPM 02) (ps.gz | ps)
¶  Automatic time-bound analysis for a higher-order language (GL-PEPM 02) (ps.gz | ps)
¶  Automated software engineering using concurrent class machines (GLSSY-ASE 01) (ps.gz | ps)
¶  Solving regular tree grammar based constraints (LLS-SAS 01) (ps.gz | ps)
¶  Automatic live memory analysis for garbage-collected languages (USL-LCTES 01) (ps.gz | ps)
¶  From recursion to iteration: what are the optimizations? (LS-PEPM 00) (ps.gz | ps | slides.ps.gz | slides.ps)
¶  Efficiency by incrementalization: an introduction (Liu-HOSC 00) (ps.gz | ps)

Software Systems copyright notice

¶  MultiRunner and MultiQuery. Assistants for traversing links and answering queries on the Web. SUNY Stony Brook, 2001-.

¶  CCM VP. A visual frontend and an optimized-code generator for a powerful modeling language called concurrent class machines. SUNY Stony Brook, 2001-.

¶  CACHET continued. Powerful program optimization based on automated incrementalization. Indiana University and SUNY Stony Brook, 1997-.

¶  ALPA. Automatic language-based performance analysis for computing worst-case bounds on running times and space usage. Indiana University and SUNY Stony Brook, 1997-.

¶  CACHET. An incremental-attribution-based interactive system that uses systematic program analysis and transformation techniques to derive efficient incremental programs. Department of Computer Science, Cornell University, 1993-1996.

¶  OGGEB. An expert system for evaluation of oil and gas generation in basins, with interfaces to several graphical tools for geochemical analysis. Research Institute of Oil Exploration and Development Science (CD-RIED) and Tsinghua University, 1988-1990.

Research Project: Incrementalization for Efficiency Improvement [some MS projects]

Pervasive, intensive, and critical computations today require computer software to be highly efficient and reliable. Studies on this topic span almost all branches of computer science but have been relatively isolated in each area. The goal of our work has been to bring all techniques together in order to develop general systematic approaches and supporting tools for improving the efficiency of computations and facilitating the assurance of their correctness. This has involved exploring program analysis and transformation techniques and domain-specific knowledge for incrementalization.

Incrementalization transforms batch programs into efficient and correct incremental programs that exploit (1) the result of, (2) the intermediate results computed in, and (3) auxiliary information about a previous computation. Since every non-trivial computation proceeds by iteration or recursion, the approach can be used for achieving efficient computations by incrementalizing loops and recursions. This method has been applied to problems in list processing, graph algorithms, VLSI design, image processing, database queries, program analysis, and so on, which were previously solved in ad hoc and often error-prone ways. A prototype system, Cachet, for incrementalization has been under development. New methods for program dependence analysis and time and space analysis have been studied to support incrementalization and other program manipulation needs. An overview of all work is given below. A description with more details about the earlier parts was given earlier.

Work is in progress on refining all analysis and transformation aspects of the incrementalization approach to provide programming methods and compiler technologies for drastic program optimizations. Based on techniques of the Synthesizer Generator and APTS, originally developed by the groups of Professor Tim Teitelbaum at Cornell and Professor Bob Paige at NYU, respectively, we are also studying implementation frameworks and algorithms that support efficient, complex program analyses and transformations. As an application, we are investigating issues, including incremental state updates and interplay between optimization and abstraction (via objects and classes, components, or modules), for generating efficient code from higher-level, more declarative specifications for reactive systems and complex data manipulation systems. Another goal of this research is to develop methods for parallel and concurrent computations by incrementalizing across processors and analyzing asynchronous computations.

These projects have been supported in part by ONR, NSF, Motorola, etc. Some of them have been performed jointly with colleagues Radu Grosu, Steve Johnson, Bob Paige, Scott Smolka, Scott Stoller, and Tim Teitelbaum and PhD students Gustavo Gomez, Michael Gorbovitski, Katia Hristova, Ning Li, Byron Long, Tom Rothamel, Leena Unnikrishnan, Sean Yu, and Yuchen Zhang.

Courses and Seminars copyright notice

¶  CSE315 (Spring `06): Database Transaction Processing Systems, Stony Brook

¶  CSE690 (Spring `06): Program Design and Optimization, Stony Brook

¶  CSE526 (Spring `05): Principles of Programming Languages, Stony Brook

¶  CSE591 (Spring `05): Security Policy Frameworks, Stony Brook

¶  CSE/ISE308 (Fall `04): Software Engineering, Stony Brook

¶  CSE391 (Spring `04): Web Queries: Methods and Tools, Stony Brook

¶  CSE626 (Spring `03): Advanced Programming Languages, Stony Brook

¶  CSE532 (Fall `02): Advanced Database Systems, Stony Brook

¶  CSE/ISE305 (Spring `02): Principles of Database Systems, Stony Brook

¶  CSE/ISE308 (Fall `01): Software Engineering, Stony Brook

¶  CSE667 (Fall `01): Design and Analysis Research Seminar, Stony Brook

¶  CSE526 (Spring `01): Principles of Programming Languages, Stony Brook

¶  CSE675 (Fall `00): Program Transformation and Program Analysis, Stony Brook

¶  B629 (Fall `99): Language-Based Algorithm Design and Analysis, Indiana U.

¶  P523 (Spring `99): Programming Language Implementation, Indiana U.

¶  B629 (Spring `99): Program Analysis and Program Transformation, Indiana U.

¶  (Spring `99): Computer Science Department Colloquium, Indiana U.

¶  C212/A592 (Fall `98): Introduction to Software Systems (using Java), Indiana U.

¶  (Fall `98): Computer Science Department Colloquium, Indiana U.

¶  B629 (Spring `98): Language-Based Performance Analysis and Improvement, Indiana U.

¶  C212/A592 (Fall `97): Introduction to Software Systems (using Java), Indiana U.

¶  B403 (Spring `97): Introduction to Algorithm Design and Analysis, Indiana U.

¶  B629 (Spring `97): Program Transformation and Programming Environments, Indiana U.

¶  (Fall `96): Programming Languages Seminar, Indiana U.

¶  LCTES 2006: ACM SIGPLAN/SIGBED 2006 Conference on Languages, Compilers, and Tools for Embedded Systems, Ottawa, Canada, June 14-16, 2006.

¶  PLAS 2006: ACM SIGPLAN 2006 Workshop on Programming Languages and Analysis for Security, Ottawa, Canada, June 10, 2006.

¶  PEPM 2006: ACM SIGPLAN 2006 Workshop on Partial Evaluation and Program Manipulation, Charleston, South Carolina, January 9-10, 2006.

¶  SCOPES 2005: The 9th International Workshop on Software and Compilers for Embedded Systems, Dallas, Texas, September 29-October 1, 2005.

¶  LCTES 2005: ACM SIGPLAN/SIGBED 2005 Conference on Languages, Compilers, and Tools for Embedded Systems, Chicago, Illinois, June 15-17, 2005.

¶  WG2.1 Meeting: The 60th Meeting of IFIP Working Group 2.1 on Algorithmic Languages and Calculi, Monterey Bay, California, May 21-26, 2005.

¶  Some past events; plus one for a PLDI PC meeting, Portland OR, Jan. 19, 2002: taxi | firetruck | passengers

¶  CS Bib: The Collection | DBLP | Dictionary: FOLDOC | Other: Compiler Construction Tools | W3C

¶  Computing Societies: ACM  SIGPLAN  SIGSOFT  SIGMOD | IEEE  CS  TC-RTS | IFIP  TC2  WG2.1 | EAPLS | CRA

¶  News: C-SPAN | New York Times | CNN Interactive

¶  Info Lookup: AnyWho | BigYellow | CityNet Excite Travel

¶  Web Search Engines: MultiText | Google | Alta Vista | Yahoo | Inktomi | Teoma

¶  Dictionary: OneLook | Conversion: Online Conversion

¶  Directions to my office | My PGP public key | My previous homepage at Indiana University

---

Copyright notice: These materials are presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

---

Last updated: April 4, 2006. Annie Liu