IMDEA Software

IMDEA initiative

Home > News > 2020 > Elena Gutiérrez's defended her thesis: "New Perspectives on Classical Automata Constructions"

October 9, 2020

Elena Gutiérrez's defended her thesis: "New Perspectives on Classical Automata Constructions"

Research Results

The researcher of the IMDEA Software Institute, Elena Gutiérrez, supervised by Pierre Ganty, defended recently her thesis titled: “New Perspectives on Classical Automata Constructions”.

She focuses in this thesis on the models of finite-state automata, pushdown automata and context-free grammars. These models have been proved useful for a wide number of applications such as program verification, natural language processing tasks or digital-image compression techniques. These applications strongly rely on language-theoretical notions where, still today, many questions are open.

The goal of this thesis is to give new theoretical perspective on a collection of open problems, that are at the core of classical automata constructions and well-established algorithms.

The underlying mathematical tool to approach these questions are equivalence relations on words as abstractions of languages. So, she studies three main questions:

In this thesis, she aims to get a better understanding of the language-theoretical basis of the double-reversal method and its connection with the partition-based techniques. As a result, we provide a uniform framework of deterministic automata constructions based on finite-index equivalences on words that allows us to give a new simple proof of the double-reversal method and shed light on the relation between this algorithm and the partition-based techniques.

Her main contribution is to provide an infinite family of PDAs defined over a singleton alphabet that allows her to extract lower bounds on the number of grammar variables of the smallest CFG.

To sum up, “in this dissertation we leverage equivalences on words as abstractions of languages. More pointedly, these abstractions are regular approximations of languages. Our results regarding finite-index congruences encourages the study of other kinds of regular approximations of context-free languages and the use of our framework to define congruence-based automata constructions for their finite representation”, appointed Elena. On the other hand, her work on the Parikh equivalence assumption shows that, despite being a relaxed version of language equivalence that enables the analysis of certain complex systems, when comparing PDAs against CFGs the situation is not different to that of language equivalence. And also, sets the basis for future directions on the extension of Parikh’s Theorem to weighted automata.