CS Colloquium Series @ UCY
Department of Computer Science - University of Cyprus
The Department of Computer Science at the University of Cyprus holds research colloquiums and social hours approximately once weekly. All university students, faculty, and staff are invited to attend. Notifications about new and upcoming events are automatically disseminated to a variety of institutional lists.
If you don't receive these notifications, but want to get informed about upcoming colloquium announcements, you can do the following:
List
RSS
Directions
Colloquium Coordinator: Demetris Zeinalipour
Colloquium: Small Sweeping 2NFAs Are Not Closed Under Complement, Dr. Christos Kapoutsis (University of Cyprus, Cyprus), Friday, April 3, 2009, 15:00 - 16:00 EET.
The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:
Small Sweeping 2NFAs Are Not Closed Under Complement
 |
Speaker: Dr. Christos Kapoutsis |
Abstract:
Understanding the power of nondeterminism is one of the major goals of the theory of computation. The most important problem in this respect is the famous P vs NP question: does nondeterminism make a difference on Turing machines that use only "small" (i.e., polynomial) time? Another important problem is the L vs NL question: does nondeterminism make a difference on Turing machines that use only "small" (i.e., logarithmic) space? In 1978, Sakoda and Sipser proposed the following analogue to these questions: instead of full-fledged Turing machines, focus only on those which cannot write on their tape; instead of time or space, focus on size. That is: does nondeterminism make a difference on two-way finite automata that use only a "small" (i.e., polynomial) number of states? Also known as the 2D vs 2N question, where 2D (resp., 2N) is the class of problems that can be solved by small deterministic (resp., nondeterministic) two-way finite automata, this problem remains open. The conjecture is that indeed 2D and 2N are different. Given that 2D is closed under complement, one way to confirm the conjecture is to show that this closure fails for 2N; namely, that complementing a nondeterministic two-way finite automaton involves an exponential blow-up in the number of states, in general. In this colloquium, we will sketch a proof of this claim for the special case of automata that are sweeping, in the sense that they can change the direction of their head only at the two ends of the tape.
Short Bio:
Christos Kapoutsis began his graduate studies at MPLA, Athens and continued to receive his PhD from the MIT EECS Department in 2006, for work on the size complexity of finite automata. After two years as a postdoctoral researcher at the Chair for Information Technology and Education at ETH, he is now a visiting lecturer at the Department of Computer Science, University of Cyprus.
Sponsor: The CS Colloquium Series is supported by a generous donation from  |