---

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  [a more complete list] [DBLP] [Google Scholar]

¶  Y. A. Liu and S. D. Stoller. From Datalog Rules to Efficient Programs with Time and Space Guarantees. ACM Transactions on Programming Languages and Systems (TOPLAS), 31(6)1-38, August 2009. (at ACM |pdf)     An earlier version appeared in Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP), 2003. (at ACM |ps.gz |pdf)

¶  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 |pdf |slides.ps.gz)

¶  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 |pdf)     An earlier version appeared in Proceedings of the 8th European Symposium on Programming (ESOP), 1999. (at Springer |abstract |ps.gz |pdf |slides.ps.gz)

¶  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 |pdf)     An earlier version appeared in Proceedings of the 6th International Static Analysis Symposium (SAS), 1999. (at Springer |abstract |ps.gz |pdf)

¶  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 |pdf)     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 |pdf)

¶  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 |pdf)     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 |pdf)

¶  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 |pdf)     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 |pdf)

¶  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 |pdf)

Some recent technical reports:
¶  From clarity to efficiency for distributed algorithms (LSLG-OOPSLA 12) (pdf)
¶  High-level executable specifications of distributed algorithms (LSL-SSS 12) (pdf)
¶  More efficient Datalog queries: Subsumptive tabling beats magic sets (TL-SIGMOD 11) (pdf)
¶  Precise complexity analysis for efficient Datalog queries (TL-PPDP 10) (pdf)
¶  Graph queries through Datalog optimizations (TGL-PPDP 10) (pdf)
¶  Composing transformations for instrumentation and incrementalization (GLSR-PEPM 12) (pdf)
¶  Alias analysis for optimization of dynamic languages (GLSRT-DLS 10) (pdf)
¶  A language and framework for invariant-driven transformations (LGS-GPCE 09) (pdf)
¶  Model checking linearizability via refinement (LCLS-FM 09) (pdf)
¶  From Datalog rules to efficient programs with time and space guarantees (LS-TOPLAS 09) (pdf)
¶  Generating incremental implementations of object-set queries (RL-GPCE 08) (pdf)
¶  Analysis and transformations for efficient query-based debugging (GTRSL-SCAM 08) (pdf)
¶  Generating specialized rules and programs for demand-driven analysis (THL-AMAST 08) (pdf)
¶  Efficient runtime invariant checking: A framework and case study (GRLS-WODA 08) (pdf)
¶  Efficient trust management policy analysis from rules (HTL-PPDP 07) (pdf)
¶  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-ONR book 07) (slightly revised: 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) (ps.gz |pdf)
¶  Iterate, incrementalize, and implement: A systematic approach to efficiency improvement and guarantees (Liu-ICC 03, abstract for an invited talk) (ps.gz |pdf)
¶  Optimizing Ackermann's function by incrementalization (LS-PEPM 03) (ps.gz |pdf)
¶  Optimized live heap bound analysis (USL-VMCAI 03) (ps.gz |pdf)
¶  A systematic incrementalization technique and its application to hardware design (JLZ-STTT 03) (ps.gz |pdf)
¶  Solving regular path queries (LY-MPC 02) (ps.gz |pdf)
¶  Program optimization using indexed and recursive data structures (LS-PEPM 02) (ps.gz |pdf)
¶  Automatic time-bound analysis for a higher-order language (GL-PEPM 02) (ps.gz |pdf)
¶  Automated software engineering using concurrent class machines (GLSSY-ASE 01) (ps.gz |pdf)
¶  Solving regular tree grammar based constraints (LLS-SAS 01) (ps.gz |pdf)
¶  Automatic live memory analysis for garbage-collected languages (USL-LCTES 01) (ps.gz |pdf)
¶  From recursion to iteration: what are the optimizations? (LS-PEPM 00) (ps.gz |pdf |slides.ps.gz)
¶  Efficiency by incrementalization: an introduction (Liu-HOSC 00) (ps.gz |pdf)

---

Software Systems copyright

¶  DistAlgo. A language for distributed algorithms. Stony Brook University, 2010-.

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

¶  A system for generating efficient implementations from Datalog rules. SUNY Stony Brook, 2003-.

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

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

¶  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 Jon Brandvein, Gustavo Gomez, Michael Gorbovitski, Katia Hristova, Ning Li, Bo Lin, Byron Long, Tom Rothamel, Tuncay Tekle, Leena Unnikrishnan, Sean Yu, and Yuchen Zhang.

---

Research Overview

• Incrementalization: deriving incremental programs, with respect to input change operations, that use
  • 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).
• Optimization: generating efficient implementations by incrementalizing expensive computations for
  • loops (IFIP 97) and aggregate array computations (ICCL 98a / TOPLAS 05),
  • recursive functions (ESOP 99 / HOSC 03, PEPM 00, PEPM 02a, PEPM 03),
  • rules and queries (PPDP 03 / TOPLAS 09, AMAST 08, PPDP 10a, SIGMOD 11),
  • set expressions (see PEPM 06, PEPM 97, see TR 15 in prep),
  • and objects (OOPSLA 05, GPCE 08, TR 15 in prep),
  • with an overview of all five (TR 13 / book 13).
• Program dependence analysis: dead-code analysis, a.k.a. slicing, on recursive data using
  • 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).
• Program analysis for dynamic object-oriented languages, including
  • control flow analysis, type analysis, and alias analysis (DLS 10).
• Program running time and space analysis for
  • time bound and general cost bound (LCTES 98 / TC 01),
  • time bound for higher-order functions (PEPM 02b),
  • live memory bound for garbage-collected languages (LCTES 01, VMCAI 03),
  • stack space bound and heap allocation bound (TR 00),
  • and time and space complexities of implementations of Datalog (see PPDP 03 / TOPLAS 09, see PPDP10a, see SIGMOD 11).
• Applications of optimization by incrementalization for
  • combinatorial optimization, string and graph algorithms (see PEPM 95 / TOPLAS 98, see POPL 96 / SCP 01, see ESOP 99 / HOSC 03, see PEPM 02a, see PEPM 03)
  • hardware design and verification (see IFIP 97, CHARME 99 / STTT 03)
  • image processing (see ICCL 98a / TOPLAS 05)
  • code generation for reactive systems (see ASE 01, see LCTES 06)
  • graph queries (see MPC 02, see PLDI 04, PPDP 10b)
  • role-based access control (PEPM 06, see PEPM 12)
  • type inference for secure information flow analysis (PLAS 06)
  • trust management policy analysis (PPDP 07)
  • runtime invariant checking (WODA 08, see GPCE 09)
  • query-based debugging (SCAM 08, see GPCE 09)
  • semantic web and ontology queries (see PPDP 10a, see SIGMOD 11)
  • demand-driven pointer analysis (see SIGMOD 11)
  • instrumentation of BitTorrent (see PEPM 12)
  • network flow queries (see PEPM 12)
  • distributed algorithms (see OOPSLA 12)
• Implementations of program transformations and analyses, besides described in papers above:
  • a system for deriving incremental programs (KBSE 95, ICFP 98 poster)
  • a language and framework for invariant-driven transformations (GPCE 09, PEPM 12)
• Other work:
  • uncertainty reasoning and expert systems (IFSA 89, ...)
  • incremental algorithms for optimal line-breaking in text layout (TR 92 / US Patent No. 6647533)
  • system performance monitoring survey (Wiley 99, Wiley 08)
  • efficient property detection for distributed systems (CAV 98, CAV 00)
  • model checking distributed Java programs (SPIN 01)
  • concurrent class machines (ASE 01)
  • regular path queries (MPC 02) and parametric regular path queries (PLDI 04)
  • querying complex graphs (PADL 06, see PPDP 10b)
  • generating optimized code from state-machine specifications (LCTES 06)
  • simplified specification of role-based access control (ONR 07)
  • model checking linearizability (FM 09 / TSE 13)
  • high-level executable specifications of distributed algorithms (SSS 12)

---

Courses and Seminars copyright

¶  CSE 505: Computing with Logic Stony Brook, Spring 2024.

¶  CTI 102: What's Logical, was ITS102 for 2017 and 2021, Stony Brook, Spring 2017, 2021, 2023, 2024.

¶  CSE645: Seminar in Languages, Stony Brook, every semester, Spring 2008, Fall 2028, ..., Spring 2024.

¶  CSE307: Principles of Programming Languages, Stony Brook, Spring 2007, 2009, 2011, 2012, 2014, 2023.

¶  CSE526: Principles of Programming Languages, Stony Brook, Spring 2001, 2005, 2021, 2022.

¶  CSE215: Foundations of Computer Science, Stony Brook, Spring 2020.

¶  CSE535: Asynchronous Systems, Stony Brook, Fall 2012, 2013, 2015, 2018.

¶  CSE591: Programming Complex Algorithms, Stony Brook, Fall 2016.

¶  CSE393: Concurrent and Distributed Algorithms, Stony Brook, Spring 2012, 2015.

¶  CSE690: Concurrent and Distributed Algorithms, Stony Brook, Spring 2011, 2012, 2015.

¶  CSE392: Data Mining, Stony Brook, Fall 2014.

¶  CSE614: Advanced Programming Languages, Stony Brook, Spring 2008, 2010, Fall 2013.

¶  CSE373/MAT373: Analysis of Algorithms, Stony Brook, Fall 2012.

¶  CSE/ISE308: Software Engineering, Stony Brook, Fall 2001, 2004, Spring 2010.

¶  CSE592: Protocol Design and Analysis, Stony Brook, Spring 2009.

¶  ITS102: How to Solve Them, Stony Brook, Spring 2007, 2008, 2009.

¶  CSE/ISE315: Database Transaction Processing Systems, Stony Brook, Spring 2006.

¶  CSE690: Program Design and Optimization, Stony Brook, Spring 2006.

¶  CSE591: Security Policy Frameworks, Stony Brook, Spring 2005.

¶  CSE391: Web Queries: Methods and Tools, Stony Brook, Spring 2004.

¶  CSE352: Artificial Intelligence, Stony Brook, Spring 2003.

¶  CSE626: Advanced Programming Languages, Stony Brook, Spring 2003.

¶  CSE532: Advanced Database Systems, Stony Brook, Fall 2002.

¶  CSE/ISE305: Principles of Database Systems, Stony Brook, Spring 2002.

¶  CSE667: Design and Analysis Research Seminar, Stony Brook, Fall 2001.

¶  CSE675: Program Transformation and Program Analysis, Stony Brook, Fall 2000.

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

¶  (Fall 1998, Spring 1999): Computer Science Department Colloquium, Indiana U.

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

¶  B629 (Spring '98): Language-Based Performance Analysis and Improvement, 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

¶  AMS SS 2013: Joint Mathematics Meetings AMS Special Session on Mathematical Underpinnings of Multivariate Complexity Theory and Algorithm Design, and Its Frontiers and the Field of Incrementalization, San Diego, CA, January 9-12, 2013.

¶  ESOP 2013: The 23nd European Symposium on Programming, Rome, Italy, March 16-24, 2013.

¶  GPCE 2012: The 11th International Conference on Generative Programming and Component Engineering, Dresden, Germany, September 24-27, 2012.

¶  Datalog 2.0: The Datalog 2.0 Workshop, Vienna, Austria, September 11-13, 2012.

¶  LCTES 2012: ACM SIGPLAN/SIGBED 2012 Conference on Languages, Compilers, Tools and Theory for Embedded Systems, Beijing, China, June 12-13, 2012.

¶  LADA 2012: Workshop on Languages for Distributed Algorithms, Philadelphia, USA, January 23-24, 2012 (with POPL 2012).

¶  GPCE 2011: The 10th International Conference on Generative Programming and Component Engineering, Portland, Oregon, October 22-23, 2011 (collocated with SPLASH 2011).

¶  LOPSTR 2011: The 21st International Symposium on Logic-Based Program Synthesis and Transformation, Odense, Denmark, July 18-20, 2011.

¶  SCOPES 2011: The 14th International Workshop on Software and Compilers for Embedded Systems, Schloss Rheinfels, St. Goar, Germany, June 27-28, 2011

¶  LCTES 2011: ACM SIGPLAN/SIGBED 2011 Conference on Languages, Compilers, Tools and Theory for Embedded Systems, Chicago, IL, April 12-14, 2011.

¶  CC 2011: The 20th International Conference on Compiler Construction, Saarbrucken, Germany, March 26-April 4, 2011.

¶  WG2.1 Meeting: The 66th Meeting of IFIP Working Group 2.1 on Algorithmic Languages and Calculi, Atlantic City, NJ, Sept 19-24, 2010.

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

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

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

¶  Directions to my office

---

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.