ジョヴァンニ・ピギッツィーニ

ジョヴァンニ・ピギッツィーニ
ジョヴァンニ・ピギッツィーニ
母校	ミラノ大学
知られている	状態の複雑さ
	科学者としてのキャリア
フィールド	理論計算機科学 ; 形式言語理論
機関	ミラノ大学

ジョヴァンニ・ピギッツィーニは、形式言語理論、特に双方向有限オートマトンの状態複雑性に関する研究で知られるイタリアの理論計算機科学者です。1993 年にミラノ大学で博士号を取得し、2001 年から同大学の教授を務めています。ピギッツィーニは、2006 年から毎年開催される「形式システムの記述的複雑性」学術会議の運営委員長を務めています。

研究貢献

Pighizziniは、1文字のアルファベット上で異なるタイプの有限オートマトン間の最適な状態複雑度のトレードオフを得ました。 ^[1]^[2]^[3]特に、GeffertおよびMereghettiとの共同論文^[2]では、Savitchの定理を使用して、双方向非決定性有限オートマトンを双方向決定性有限オートマトンでシミュレーションする最初の方法を提示し、2DFA対2NFAの未解決問題に貢献しました。Jiráskováと共同で、自己検証有限オートマトンの状態複雑度を決定しました。^[4]

彼はまた、対数的空間計算量クラス^[5]と辞書式最大文字列の検索の計算量に関する結果によって計算量理論に貢献した。 ^[6]

参考文献

^ Mereghetti, Carlo; Pighizzini, Giovanni (2001). 「単項オートマトン間の最適シミュレーション」SIAM Journal on Computing . 30 (6): 1976–1992. doi :10.1137/S009753979935431X. hdl : 2434/35121 . ISSN 0097-5397.
^ ab ゲフェルト、ヴィリアム;メレゲッティ、カルロ。ピギッツィーニ、ジョバンニ (2003)。「双方向の非決定性単項オートマトンをより単純なオートマトンに変換する」。理論的なコンピューターサイエンス。295 (1-3): 189-203。土井：10.1016/S0304-3975(02)00403-6。ISSN 0304-3975。
^ Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni (2014). 「エンドマーカーでのみ選択を行う双方向オートマトン」. 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). 「決定論的オートマトンによる自己検証オートマトンの最適シミュレーション」.情報と計算. 209 (3): 528–535. doi :10.1016/j.ic.2010.11.017. ISSN 0890-5401.
^ Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (1998). 「空間と反転に関するサブログ境界」SIAM Journal on Computing . 28 (1): 325–340. doi :10.1137/S0097539796301306. hdl : 2434/178756 . ISSN 0097-5397. S2CID 37853723.
^ Allender, Eric; Bruschi, Danilo; Pighizzini, Giovanni (1993). 「最大単語関数の計算の複雑さ」.計算複雑性. 3 (4): 368–391. doi :10.1007/BF01275489. ISSN 1016-3328. S2CID 886700.

外部リンク

公式サイト
DBLP書誌サーバーの Giovanni Pighizzini

[MereghettiPighizzini2001-1] Mereghetti, Carlo; Pighizzini, Giovanni (2001). 「単項オートマトン間の最適シミュレーション」SIAM Journal on Computing . 30 (6): 1976–1992. doi :10.1137/S009753979935431X. hdl : 2434/35121 . ISSN 0097-5397.

[GeffertMereghetti2003-2] ゲフェルト、ヴィリアム;メレゲッティ、カルロ。ピギッツィーニ、ジョバンニ (2003)。「双方向の非決定性単項オートマトンをより単純なオートマトンに変換する」。理論的なコンピューターサイエンス。295 (1-3): 189-203。土井：10.1016/S0304-3975(02)00403-6。ISSN 0304-3975。

[GeffertGuillon2014-3] Geffert, Viliam; Guillon, Bruno; Pighizzini, Giovanni (2014). 「エンドマーカーでのみ選択を行う双方向オートマトン」. Information and Computation . 239 : 71–86. arXiv : 1110.1263 . doi :10.1016/j.ic.2014.08.009. ISSN 0890-5401.

[JiráskováPighizzini2011-4] Jirásková, Galina; Pighizzini, Giovanni (2011). 「決定論的オートマトンによる自己検証オートマトンの最適シミュレーション」.情報と計算. 209 (3): 528–535. doi :10.1016/j.ic.2010.11.017. ISSN 0890-5401.

[GeffertMereghetti1998-5] Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (1998). 「空間と反転に関するサブログ境界」SIAM Journal on Computing . 28 (1): 325–340. doi :10.1137/S0097539796301306. hdl : 2434/178756 . ISSN 0097-5397. S2CID 37853723.

[AllenderBruschi1993-6] Allender, Eric; Bruschi, Danilo; Pighizzini, Giovanni (1993). 「最大単語関数の計算の複雑さ」.計算複雑性. 3 (4): 368–391. doi :10.1007/BF01275489. ISSN 1016-3328. S2CID 886700.