Talks & Seminars
Title: Interplay Between Language Classes and Complexity Classes
Ms. Nutan Limaye, Research Fellow, Institute of Mathematical Sciences, Chennai
Date & Time: January 30, 2009 16:00
Venue: Conference Room, 01st floor, ā€˜Cā€™ Block, Kanwal Rekhi Building

Fix an automaton M. Given an input string w, the membership problem for M deals with checking if w belongs to the language accepted by M. he corresponding counting problem deals with computing the number of accepting paths in machine M on string w.

We consider a restriction on CFLs called height determinism. This is a useful restriction, defined by Nowotka and Srba [NS07]. We analyse the complexity of membership problem and counting problem for this class. We show that the counting problem for this has the same complexity as the membership problem, LogDCFL. We also consider multi-pushdown systems with a weaker notion of height determinism (visible multi-pushdown machines). They were defined by [TMP07]. We show that the membership problem for them is in LogCFL.

(Collaboration with Meena Mahajan and Antoine Meyer)
Speaker Profile:
Details about the speaker is available at http://www.imsc.res.in/~nutan/
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback