Room 327

Axiomatizing regular expressions

Kamal Lodaya

IMSc

Proving inclusion or equivalence of the languages of regular expressions has been studied since Aanderaa (1965) and Salomaa (1966), more recently by Pratt (1990) and Kozen (1995). There is a different tradition emerging
from the type-based framework of Lambek (1958), more recently Girard (1984), Abrusci (1989), Brown and Gurr (1995). There also have been infinite axiomatizations by Buszkowski (2006) and Palka (2007). We will discuss these ideas.