News

Fri, Feb. 12, 2010

Budget for Spring 2010 semester:

Weekly Seminar & Tea-Time   $500

Guest Speakers: honorarium and travel   $600

End of Semester Lunch   $500

Total Approved: $1,600

Thu, Sep. 18, 2008

This semester's budget approved last week

The budget summary is:

Weekly Seminar, Tea-Time and book purchases: $1305

Guest speakers: honrarium and travel: $400

Welcome Back Lunch: $560

Farewell Dinner: $560

Karaoke: $450

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 compilers to 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.