Giovanni Pighizzini is an Italian
theoretical computer scientist
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the th ...
known for his work in
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
and particularly in
state complexity State complexity is an area of theoretical computer science
dealing with the size of abstract automata,
such as different kinds of finite automata.
The classical result in the area is that
simulating an n-state
nondeterministic finite automaton
by ...
of
two-way finite automata. He earned his PhD in 1993 from the
University of Milan
The University of Milan ( it, Università degli Studi di Milano; la, Universitas Studiorum Mediolanensis), known colloquially as UniMi or Statale, is a public research university in Milan, Italy. It is one of the largest universities in Europe ...
, 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
An academic conference or scientific conference (also congress, symposium, workshop, or meeting) is an event for researchers (not necessarily academics) to present and discuss their scholarly work. Together with academic or scientific journal ...
since 2006.
Research contributions
Pighizzini obtained optimal
state complexity State complexity is an area of theoretical computer science
dealing with the size of abstract automata,
such as different kinds of finite automata.
The classical result in the area is that
simulating an n-state
nondeterministic finite automaton
by ...
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 o ...
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 State complexity is an area of theoretical computer science
dealing with the size of abstract automata,
such as different kinds of finite automata.
The classical result in the area is that
simulating an n-state
nondeterministic finite automaton
by ...
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 relating these classes to each other. A computational problem is a task solved ...
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)