Recent News

• Fri, Jan. 18, 2008.
  The first officers' meeting this semester discussed budget, Welcome Back Lunch and the department library issues

  See the meeting minutes and the suggested structure of the library database for details.

• Fri, Apr. 27, 2007.
  Our congratulations to Parisa Babaali, who defended her PhD thesis today!

  Parisa's thesis is titled "Generic and Structural Properties of Random Automata" and is devoted to finite automata generated at random. A finite automaton is an abstract machine with finitely many states, that reads a "word" as its input, and either does or does not "recognize" it. The collection of words that are recognized by a finite automaton is called a regular language. The application of finite automata and regular languages ranges from compilersto certain problems in abstract algebra and cryptography. The interest in randomly generated automata comes from generic complexity and cryptography, which are concerned with those properties that are characteristic of most automata, though must not be pertinent to all of them. A particular interest is in "generic" properties, that is those that are observed with probability one.

  In her thesis, Parisa introduced and studied a novel method for randomly constructing automata based on the breadth-first spanning tree. Using the developed method, Parisa estimated probabilities of obtaining finite automata with certain properties. In particular, she proved that automata which recognize exponential languages are asymptotically generic. (A language is exponential if the number of words of a given length in this language increases exponentially with the length.) Parisa also established an upper bound on the probability of minimal automata. Knowing this probability would help translate results obtained for finite automata to the corresponding regular languages.