Yanhong Annie Liu

Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Yanhong Annie Liu

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] [Spring 07: Programming Languages | How to Solve Them ] [Other Pointers]

Research Interests

My primary research interests are in the areas of programming languages, compilers, and software systems. I am particularly interested in general and systematic methods for improving computation efficiency and software productivity. This includes (1) program analysis and transformation techniques for incremental computation and for parallel and concurrent computation, (2) applications in optimizing compilers, language-based interactive systems, real-time and reactive systems, algorithm design, program development, and software maintenance, and (3) supporting tools and user interfaces that allow convenient and efficient implementation of program analyses and transformations and facilitate their applications. My major research project, Incrementalization for Efficiency Improvement, together with derived projects, mainly on program dependence analysis and time and space analysis, encompasses all three aspects above.

I have strong other interests in database management, semantic web, distributed systems, and security. These include, in particular, query languages and query optimization, incremental view maintenance, intelligent information retrieval, property detection for distributed systems, systematic approaches for fault-tolerance, information flow analysis, and access control and trust management frameworks. I have also worked on uncertainty reasoning and expert systems.

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. Special issue in memory of Bob Paige. (at Springer |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:
¶ Efficient implementation of tuple pattern based retrieval (RL-PEPM 07) (pdf)
¶ 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)
¶ 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)

[a more complete list] [my ftp directory]

Software Systems copyright notice

¶ InvTL/InvTS. An invariant-driven program transformation language and system. SUNY Stony Brook, 2005-.

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

¶ ALPA. An automatic language-based performance analysis system that generates accurate worst-case time and space given bounds on input sizes. Indiana University and SUNY Stony Brook, 1997-.

¶ CACHET continued. A program transformation system for drastic program optimization based on automated incrementalization and powerful program analysis. Indiana University, 1997-2000.

¶ CACHET. An incremental-attribution-based interactive system that uses systematic program analysis and transformation techniques to derive efficient incremental programs. 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 Petroleum Exploration and Development (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.

[some MS projects]

Research Overview

the return values (SCP 95),
the intermediate results (PEPM 95 / TOPLAS 98),
and auxiliary information (POPL 96 / SCP 01),
with an overview of all three (HOSC 00).

optimize loops (IFIP 97) and aggregate array computations (ICCL 98a / TOPLAS 05),
optimize expensive recursive functions (ESOP 99 / HOSC 03, PEPM 02a, PEPM 03),
transform recursion into iteration (PEPM 00),
generate efficient algorithms and implementations from rules (PPDP 03),
and optimize across object abstraction (OOPSLA 05).

abstract interpretation on fixed domains (see PEPM 95 / TOPLAS 98),
abstract interpretation on regular tree grammar domains (ICCL 98b),
or regular tree grammar based constraints (SAS 99 / SCP 03),
with efficient algorithms for solving the grammar-based constraints (SAS 01).

time-bound and general cost-bound analysis (LCTES 98 / TC 01)
higher-order time-bound analysis (PEPM 02b)
analysis of live memory bound for garbage-collected languages (LCTES 01, VMCAI 03)
analyses of stack space bound and heap allocation bound (TR 00)

hardware design and verification (see IFIP 97, CHARME 99 / STTT 03)
image processing (see ICCL 98a / TOPLAS 05)
combinatorial optimization, string and graph algorithms (see PEPM 95 / TOPLAS 98, see POPL 96 / SCP 01, see ESOP 99 / HOSC 03, see PEPM 02a)
code generation for reactive systems (see ASE 01, see LCTES 06)
query implementation and optimization (see MPC 02, see PLDI 04, see PADL 06)
model checking push-down systems (see VMCAI 06)
implementations of role-based access control (see PEPM 06)
secure information flow analysis (see PLAS 06)

for deriving incremental programs (KBSE 95, ICFP 98 poster)
for optimizing aggregate array computations over loops (see TOPLAS 05)
for constraints-based dead-code analysis (see SAS 99 / SCP 03)
for analyzing time and space bounds (see LCTES 98 / TC 01, see PEPM 02b, see LCTES 01, see VMCAI 03, see TR 00)
for generating efficient implementations from rules (to be reported)
for optimization across object abstraction (see OOPSLA 05)

efficient implementation of tuple pattern based retrieval (PEPM 07)
generating optimized code from SCR specifications (LCTES 06)
type inference for secure information flow (PLAS 06)
querying complex graphs (PADL 06)
efficient implementations of core role-based access control (PEPM 06)
specification of role-based access control (TR 05)
linear temporal logic model checking of push-down systems (VMCAI 06)
solving regular path queries (MPC 02) and parametric regular path queries (PLDI 04)
concurrent class machines (ASE 01)
model checking distributed Java programs (SPIN 01)
efficient property detection for distributed systems (CAV 98, CAV 00)
system performance monitoring survey (Wiley 99)
incremental algorithms for optimal line-breaking in text layout (TR 92 / US Patent No. 6647533)
uncertainty reasoning and expert systems (IFSA 89, ...)

Courses and Seminars copyright notice

¶ CSE307 (Spring `07): Principles of Programming Languages, Stony Brook

¶ ITS102 (Spring `07): How to Solve Them, Stony Brook

¶ CSE/ISE315 (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

¶ CSE352 (Spring `03): Artificial Intelligence, 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.

Other Pointers

¶ APLAS 2007: The Fifth ASIAN Symposium on Programming Language and Systems, Singapore, November 29-December 1, 2007.

¶ LCTES 2007: ACM SIGPLAN/SIGBED 2007 Conference on Languages, Compilers, and Tools for Embedded Systems, San Diego, California, June 13-15, 2007.

¶ SCOPES 2007: The 10th International Workshop on Software and Compilers for Embedded Systems, Nice, France, April 20, 2007.

¶ PEPM 2007: ACM SIGPLAN 2007 Workshop on Partial Evaluation and Program Manipulation, Nice, France, January 14-15, 2007.

¶ WG2.1 Meeting: The 62th Meeting of IFIP Working Group 2.1 on Algorithmic Languages and Calculi, Namur, Belgium, December 11-15, 2006.

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

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

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

¶ Dictionary: OneLook | dictionary.com | Encyclopedia: Wikipedia | Conversion: Online Conversion | Maps: Mapquest

¶ 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: January 23, 2007. Annie Liu