# Some Extentsions to the Theory of Regularity in Formal Languages

## Speaker:

Ajesh Babu School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road

## Time:

Friday, 25 June 2010 (All day)

## Venue:

• A-212 (STCS Seminar Room)

In formal languguage theory, regularity is a robust notion having many equivalent representations: regular expressions, ï¬nite state automata, MSO etc. These have made important impact on programming and veriï¬cation tools. In this talk we delve into some the alternate formulations and extensions of regularity:

1) We will look at a new representation for the $epsilon$-free fragment of regular languages by replacing the conventional concatenation operator by the chop operator, giving rise to the notion of chop expressions. We study the eï¬€ective conversions between chop expressions, regular expression and ï¬nite state automata and pin down the complexities of various decision procedures for chop expressions and its extensions. Following Salomaaâ€™s complete axiomatization of regular expressions, we provide a complete axiom system for equality chop expressions.

2) We shall survey the ï¬eld of automata over inï¬nite alphabet. This area of research aims at extending regular language theory over ï¬nite alphabet to a corresponding theory over inï¬nite alphabet. We also provide an eï¬ƒcient decision procedure for emptiness of nested data
word CMAs.

3) We shall also discuss a logspace randomized 1-pass algorithm for the membership checking of deterministic linear context-free languages.