Tata Institute of Fundamental Research
Solving Conjugacy Equation on Languages
Seminar
Speaker:
Benny George K.
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Friday, 19 Jun 2009 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
XZ=ZY is called the conjugacy equation. Given languages X and Y we are interested in knowing if there exists a non empty language Z which makes this equation true. This problem is undecidable in the general setting. We first look at X being a two element set and Y a three element set and obtain some characterizations for X and Y to be conjugates. We then extend some of those results to the case when Y is a finite set.
| Speaker: | Benny George K. School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road |
| Date: | Friday, 19 Jun 2009 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
XZ=ZY is called the conjugacy equation. Given languages X and Y we are interested in knowing if there exists a non empty language Z which makes this equation true. This problem is undecidable in the general setting. We first look at X being a two element set and Y a three element set and obtain some characterizations for X and Y to be conjugates. We then extend some of those results to the case when Y is a finite set.