Some Extentsions to the Theory of Regularity in Formal Languages

In formal languguage theory, regularity is a robust notion having many equivalent representations: regular expressions, finite state automata, MSO etc. These have made important impact on programming and verification 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 effective conversions between chop expressions, regular expression and finite 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 field of automata over infinite alphabet. This area of research aims at extending regular language theory over finite alphabet to a corresponding theory over infinite alphabet. We also provide an efficient 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.