Giovanni Pighizzini is an Italian

theoretical computer scientist Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The ACM's Special Inter ...

known for his work in

formal language theory In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet". The alphabet of a formal language consists of symbol ...

and particularly in state complexity of two-way finite automata. He earned his PhD in 1993 from the

University of Milan The University of Milan (; ), officially abbreviated as UNIMI, or colloquially referred to as La Statale ("the State niversity), is a public university, public research university in Milan, Italy. It is one of the largest universities in Eu ...

, where he is a full professor since 2001. Pighizzini serves as the Steering Committee Chair of the annual

Descriptional Complexity of Formal Systems DCFS, the International Workshop on Descriptional Complexity of Formal Systems is an annual academic conference in the field of computer science. Beginning with the 2011 edition, the proceedings of the workshop appear in the series Lecture Notes ...

academic conference An academic conference or scientific conference (also congress, symposium, workshop, or meeting) is an Convention (meeting), event for researchers (not necessarily academics) to present and discuss their scholarly work. Together with academic jou ...

since 2006.

Research contributions

Pighizzini obtained optimal state complexity tradeoffs between different types of

finite automata A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number ...

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 In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic space complexity. It states that for any space-constructable function f\in\Omega(\log(n)) ...

, 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 In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

by results on sublogarithmic space complexity classes and on the complexity of searching for a lexicographically maximal string.

References

External links

* * {{DEFAULTSORT:Pighizzini, Giovanni Italian mathematicians Italian computer scientists Living people Year of birth missing (living people)