University of Waterloo
Canada N2L 3G1
Phone: (519) 888-4567 ext. 33293
Fax: (519) 885-1208
The David Cheriton School of Computer Science offers opportunities to exceptional students through the Undergraduate Research Assistant (URA) program that allows students to earn $600 a term for part-time research with a faculty member. The money is paid once near the end of the term.
Faculty members post openings each term so interested, eligible students can apply. Students can also contact faculty members if they are interested in specific research areas to see if a URA opportunity might be available.
Any student who has completed their second year in the Faculty of Mathematics with an average of at least 80% is eligible. Preference is given to students enrolled in Computer Science major plans. A student can only do one URA per term. A student cannot be on a co-op term while doing a URA.
Title: Most complex regular languages
This URA involves research on regular languages and finite automata. The state complexity of a regular language is the number of states in the minimal deterministic finite automaton recognizing the language. Of particular interest is the state complexity of regular operations. For example, if K and L are regular languages of complexity m and n, respectively, then mn states are sufficient to recognize the union of K and L, and mn states are necessary in the worst case. Such information is useful, since it gives an indication about the amount of memory that should be available for the result of the operation.
It has been shown that certain regular languages are most complex with respect to all commonly used measures of complexity. This project will investigate most complex languages in subclasses of the class of regular languages. The work is theoretical, but may involve some computation. A short written report is required at the end of the project. Many of my URAs end up publishing papers on their projects.
Requirements: An average in CS and mathematics courses of at least 85% is required; experience shows that a lower average does not result in a successful project. This research should not interfere with your course work. Computer Science, Pure Math and C&O students are welcome to apply.
Interested students should email their resume and transcript to John Brzozowski firstname.lastname@example.org.
There are three forms that must be completed and returned to DC 3102.
A faculty member must sign and fill out the account number on both the URA form and the Casual or Additional Pay Request form.
Casual or Additional Pay Request form
Note: International students must have a Social Insurance Number (SIN) to be paid. To get a SIN:
For more information, please contact:
Office: DC 3102
Phone: (519) 888-4567 ext.32191