Sabine Broda's Annual Report
Year:
Brief description of the research activities:
- With S. Broda, A. Machiavelo and R. Reis studied the average behaviour of several complecity measures of regular expressions in star normal form using analytic combinatorics.
- With S. Broda, M. Holzer, E. Maia and R. Reis obtained new relations between several conversions from regular expressions to deterministic and non-deterministic finite automata using the notions of positions and derivatives.
- With S. Alves definition of a framework to address different kinds of problems related to type inhabitation, such as type checking, the emptiness problem, generation of inhabitants and counting, in a uniform way. Based on an alternative representation for types, called the pre-grammar of a type, different methods for these problems are defined, as well as a scheme for a decision algorithm that, for particular instantiations of the parameters, can be used to show different inhabitation related problems to be in PSPACE.