Giovanni Pighizzini - Giovanni Pighizzini

Giovanni Pighizzini
Alma materUniversity of Milan
Známý jakosložitost stavu
Vědecká kariéra
PoleTeoretická informatika
teorie formálního jazyka
InstituceUniversity of Milan

Giovanni Pighizzini je italština teoretický počítačový vědec známý svou prací v teorie formálního jazyka a zejména v složitost stavu z obousměrné konečné automaty. V roce 1993 získal titul PhD University of Milan, kde je řádným profesorem od roku 2001. Pighizzini slouží jako předseda řídícího výboru ročenky Popisná složitost formálních systémů akademická konference od roku 2006.

Výzkumné příspěvky

Pighizzini získal optimální složitost stavu kompromisy mezi různými typy konečné automaty přes jednopísmennou abecedu,[1][2][3] Zejména ve svém společném příspěvku s Geffert a Mereghetti[2] představil první simulaci obousměrné nedeterministické konečné automaty podle obousměrné deterministické konečné automaty použitím Savitchova věta, přispívající k 2DFA vs. 2NFA otevřená otázka. Společně s Jiráskovou to určil složitost stavu z samověřovací konečné automaty.[4]

Přispěl také do teorie výpočetní složitosti podle výsledků na třídách složitosti sublogaritmického prostoru[5] a na složitosti hledání lexikograficky maximálního řetězce.[6]

Reference

  1. ^ Mereghetti, Carlo; Pighizzini, Giovanni (2001). "Optimální simulace mezi unárními automaty". SIAM Journal on Computing. 30 (6): 1976–1992. doi:10.1137 / S009753979935431X. hdl:2434/35121. ISSN  0097-5397.
  2. ^ A b Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2003). "Převod obousměrných nedeterministických unárních automatů na jednodušší automaty". Teoretická informatika. 295 (1–3): 189–203. doi:10.1016 / S0304-3975 (02) 00403-6. ISSN  0304-3975.
  3. ^ Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni (2014). "Obousměrné automaty s výběrem pouze u koncových značek". Informace a výpočet. 239: 71–86. arXiv:1110.1263. doi:10.1016 / j.ic.2014.08.009. ISSN  0890-5401.
  4. ^ Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimální simulace automatických verifikačních automatů pomocí deterministických automatů". Informace a výpočet. 209 (3): 528–535. doi:10.1016 / j.ic.2010.11.017. ISSN  0890-5401.
  5. ^ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (1998). "Sublogaritmické meze vesmíru a zvraty". 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). "Složitost výpočtu maximálních slovních funkcí". Výpočetní složitost. 3 (4): 368–391. doi:10.1007 / BF01275489. ISSN  1016-3328.

externí odkazy