91´óÉñ

My research lies in the field of the theory of computation. Roughly speaking, this means I ask questions like "which problems are harder than others, and can we prove that this is true?" One can then further ask questions such as "Is this problem (efficiently) solvable in a certain framework of computation?" My work focuses primarily on the field of formal languages (sets of strings), grammars (sets of rules), and automata (rudimentary computers), and in particular, the study of a class of computational models which incorporates both nondeterminism and probability. These are two constructs which are both commonly used to model uncertainty, but which are notoriously difficult (in a strict mathematical sense!) to combine. We demonstrate that a particular interpretation of nondeterminism which utilizes multisets, rather than the traditional subsets, allows for an elegant implementation which admits both formal grammar and automaton models. This offers a resolution to a long-standing open problem, but also opens the door to further questions relative to this model of computation. Much of my time is now spent considering extensions to increase expressiveness of the model, as well as problems such as:

 

• Can we tell whether two expressions are equivalent?

• Given two automata, do they perform the same series of computations?

• What exactly and are the types of problems that can be computed by this model?

 

More broadly, I'm interested in theoretical computer science, especially problems involving logic.