Giovanni Pighizzini
Giovanni Pighizzini | |
---|---|
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.
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[]
- ^ 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.
- ^ Jump up to: a b 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
External links[]
- Official website
- Giovanni Pighizzini at DBLP Bibliography Server
- Italian mathematicians
- Italian computer scientists
- Living people