Tata Institute of Fundamental Research
Some Extentsions to the Theory of Regularity in Formal Languages
MSc Thesis Seminar
Speaker:
Ajesh Babu
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Friday, 25 Jun 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Ajesh Babu School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Friday, 25 Jun 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.