Giovanni Pighizzini

Giovanni Pighizzini is an Italian theoretical computer scientist known for his work in formal language theory and particularly in state complexity of two-way finite automata. He earned his PhD in 1993 from the University of Milan, where he is a full professor since 2001. Pighizzini serves as the Steering Committee Chair of the annual Descriptional Complexity of Formal Systems academic conference since 2006.

Research contributions

Pighizzini obtained optimal state complexity tradeoffs between different types of finite automata over a one-letter alphabet, In particular, in his joint paper with Geffert and Mereghetti

He also contributed to the computational complexity theory by results on sublogarithmic space complexity classes and on the complexity of searching for a lexicographically maximal string.