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 effective 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 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.
