A Theory of Regular Queries

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.