Giovanni Pighizzini
Alma materUniversity of Milan
Known forstate complexity
Scientific career
FieldsTheoretical Computer Science
formal language theory
InstitutionsUniversity 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.

Research contributions

Pighizzini obtained optimal state complexity tradeoffs between different types of finite automata over a one-letter alphabet,[1][2][3] In particular, in his joint paper with Geffert and Mereghetti[2] 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.[4]

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

References

  1. ↑ Mereghetti, Carlo; Pighizzini, Giovanni (2001). "Optimal Simulations between Unary Automata". SIAM Journal on Computing. 30 (6): 1976–1992. doi:10.1137/S009753979935431X. hdl:2434/35121. ISSN 0097-5397.
  2. 1 2 Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2003). "Converting two-way nondeterministic unary automata into simpler automata". Theoretical Computer Science. 295 (1–3): 189–203. doi:10.1016/S0304-3975(02)00403-6. ISSN 0304-3975.
  3. ↑ Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni (2014). "Two-way automata making choices only at the endmarkers". Information and Computation. 239: 71–86. arXiv:1110.1263. doi:10.1016/j.ic.2014.08.009. ISSN 0890-5401.
  4. ↑ Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimal simulation of self-verifying automata by deterministic automata". Information and Computation. 209 (3): 528–535. doi:10.1016/j.ic.2010.11.017. ISSN 0890-5401.
  5. ↑ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (1998). "Sublogarithmic Bounds on Space and Reversals". SIAM Journal on Computing. 28 (1): 325–340. doi:10.1137/S0097539796301306. hdl:2434/178756. ISSN 0097-5397. S2CID 37853723.
  6. ↑ Allender, Eric; Bruschi, Danilo; Pighizzini, Giovanni (1993). "The complexity of computing maximal word functions". Computational Complexity. 3 (4): 368–391. doi:10.1007/BF01275489. ISSN 1016-3328. S2CID 886700.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.