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.

Giovanni Pighizzini
Alma materUniversity of Milan
Known forstate complexity
Scientific career
FieldsTheoretical Computer Science
formal language theory
InstitutionsUniversity of Milan

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]

gollark: Am I just supposed to MANUALLY check the Maclaurin serieseseses of all the functions I use for this sort of thing?
gollark: Also, how can we prove that common special functions don't have this kind of backdoor?
gollark: See, this is what I'm worried about.
gollark: Those are probably contaminated.
gollark: I can't use them due to the Greek letter shortage.

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. 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.
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.