Faculty Recruiting Support CICS

The Theory of Vaccines

20 Apr
Tuesday, 04/20/2021 12:15pm to 1:15pm
Virtual via Zoom
Theory Seminar
Speaker: Collin Giguerre

Abstract: Despite the major role that modularity occupies in computer science, all the known results on modular analysis only treat particular problems, and there is no general unifying theory. In this paper we provide such a general theory of modularity. First, we study the space of the criteria for modularity (the so-called modularity space), and give results on its complexity. Then, we introduce the notion of vaccine and show how it can be used to completely analyze the modular space. It is also shown how vaccines can be effectively used to solve a variety of other modularity problems, providing the best solutions. As an application, we successfully apply the theory to the study of modularity for term rewriting, giving for the first time optimality results, and completely solving the modularity problem for the major properties of rewriting.

View the original paper.

Join the Zoom meeting

The CICS Theory Seminar is online, free and open to the public. If you are interested in giving a talk, please email Professor Immerman or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.