PhD in Computer Science

Finite automata have proven to be an effective tool to reason about programs operating over strings. Finite state transducers extend finite automata with outputs and can model functions from strings to strings such as natural language transformations. Due to their closure and decidability properties, these models are widely used in practice, and many extensions/improvements have been proposed.

 

Here we mainly focus on bridging the gap between the theory of automata and transducers and practical applications. Our goal is to identify applications that can be modeled using automata and transducers, and design frontend languages that allow the user to reason about his or her program. While pursuing these general goal we also end up facing new theoretical problems such as the following. Can existing models be extended to infinite alphabets? Can we extend classical finite automata minimization algorithms to work with infinite alphabets? What is the complexity of checking equivalence for a particular class of transducers?

 

We introduce novel minimization algorithms for symbolic automata over infinite alphabets that enable to efficiently generate secure passwords at random;  and Fast a domain specific language for programs that manipulate trees over complex alphabets and show how Fast can be used to optimize functional programs that operate over trees by removing intermediate computation results.