Giovanni Pighizzini
| Giovanni Pighizzini | |
|---|---|
| Residence | Italy |
| Alma mater | University of Milan |
| Known for | state complexity |
| Scientific career | |
| Fields |
Theoretical Computer Science formal language theory |
| Institutions | University of Milan |
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.
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 presented the first simulation of two-way nondeterministic finite automata by two-way deterministic finite automata using Savitch's theorem, contributing to the 2DFA vs. 2NFA open question. Jointly with Jirásková, he determined state complexity of self-verifying finite automata.
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.
...
Wikipedia