- 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
3) We shall also discuss a logspace randomized 1-pass algorithm for the membership checking of deterministic linear context-free languages.