In partial fulfillment of the Requirements for the Degree of
Master of Science
Adrian Ionescu
will defend his thesis
On the Role of Complementation in
Implicit Language Equations and Relations
Abstract
In this thesis, we solve implicit equations and relations with union and complementation. A system of relations is defined by
Li = a (X1,…,Xn), i=1,…,m1,
Li Ê a (X1,…,Xn), i= m1+1,…,m2,
Li Í a (X1,…,Xn), i= m2+1,…,m3,
where a (X1,…,Xn) are boolean functions in variables X1,…,Xn and constant languages, and Li are constant languages. Note that any group can be missing. In particular, if the second and third groups are missing we are actually solving a system of implicit equations.
We determine whether an implicit system of boolean equations or relations has solutions. If the languages Li are regular, one can give an effective construction of a (regular) solution. Moreover, we give a complete representation for all maximal and minimal solutions. We also solve the problem of uniqueness of solutions as well as whether infinitely many solutions exist.
Date: Tuesday, May 22, 2001
Time: 11:00 AM
Place: 550-PGH
Faculty, students, and the general public are invited.
Thesis Advisor: Dr. Ernst L. Leiss