# Moshe Vardi. Opening lecture: A Theory of Regular Queries

#### A Theory of Regular Queries

*Moshe Y. Vardi*

Rice University

Rice University

The classical theory of regular languages was initiated in the 1950s and reached a mature and stable state in the 1970s. In particular, the computational complexity of several decision problems for regular expressions, including emptiness, universality, and equivalence, is well understood. A new application area for regular languages emerged in the 1990s in the context of graph databases, where regular expressions provide a way to formulate queries over graphs. In this new context, the classical theory needs to be reconsidered. It turns out that the new context is a fertile area, and gives rise to an elegant theory of regular quries, which is inspired and informed, but quite different than the theory of regular languages. In this talk I will describe the class of regular queries and its well-behavedness.