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:

• First, she focuses on automata minimization algorithms, methods for finding the finite-state automaton with the minimal number of states.

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.

• Second, she addresses the question of comparing the descriptional complexity of pushdown automata (PDAs) against context-free grammars (CFGs) and finite-state automata for Parikh equivalence, a weaker notion than the standard language equivalence under which the ordering of symbols in the words is not important.

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.

• Finally, she addresses the question of extending Parikh’s Theorem to the more general model of weighted automata. It is well-known that Parikh’s Theorem does not hold for weighted languages. Thus, she studies sufficient conditions under which the Parikh property holds for weighted automata and also describes the decidability of this property and give a decision procedure for weighted CFGs with weights on the rational numbers.

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.