SDSU Department of Computer Science
  
Home Contact Us Undergraduate Student Info Graduate Student Info Faculty & Staff News & Events
News Calendar Problem of the Fortnight

March 2008 Calendar

CS Masters' Thesis Defense

Title: C Program for Enumerating Regular Languages
Speaker: Shilpa Shivagange
Date: Friday, March 21, 2008
Time: 1:00 p.m.
Location: GMCS 329
Thesis advisor: William Root

Abstract:
Various aspects of the problem of enumerating finite automata have been considered for almost fifty years, perhaps beginning with a technical memorandum on the subject by V.A. Vyssotsky at Bell Laboratories in 1959. But throughout those past fifty years, researchers in the United States (including Harary, Ginsburg, and Harrison) and in the USSR (including Livshits, Korshunov, Liskovets, Popov and Skibenko) seem to have focused entirely on problems of enumerating various types of automata, rather than enumerating the distinct languages accepted by those automata. This thesis developed a C program which, given positive integer input n , determines the number of distinct regular languages for which the unique minimal deterministic finite automaton acceptor has exactly n states.
webmaster@cs.sdsu.edu page counter College of Sciences