조반니 피기치니

Giovanni Pighizzini
조반니 피기치니
모교밀라노 대학교
로 알려져 있다.국가의 복잡성
과학 경력
필드이론 컴퓨터 과학
격식어론
기관밀라노 대학교

지오반니 피기찌니는 이탈리아의 이론 컴퓨터 과학자로, 공식 언어 이론과 특히 이원 유한 오토마타의 주 복잡성에 관한 연구로 잘 알려져 있다.그는 밀라노 대학에서 1993년 박사학위를 취득했으며, 2001년부터 전임 교수로 재직하고 있다.Pigizini는 2006년부터 매년 개최되는 형식 시스템의 복잡성 설명 학술회의 운영위원회 의장을 맡고 있다.

연구기여금

Pighizzini 유한 오토 머터의 다른 종류의 특힌one-letter alphabet,[1][2][3]에, Geffert과 Mereghetti[2]을 통해 양방향 결정성 유한 오토 머터 Savitch의 정리, contri를 사용하여 양방향 비결정론적인 플레이어와 한정되어 세포의 첫번째 시뮬레이션했다 합동 신문에 최적의 상태 복잡성 트레이드 오프를 얻었다.buting에 찾았다고e 2DFA 대 2NFA 공개 질문.지라스코바와 공동으로, 그는 유한 자동 검증의 주 복잡성을 결정했다.[4]

그는 또한 하위 로가리듬 공간 복잡성 클래스에[5] 대한 결과와 사전 편찬학적으로 최대 문자열 검색의 복잡성에 대한 결과에 의해 계산 복잡성 이론에 기여했다.[6]

참조

  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. ^ 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.
  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. S2CID 886700.

외부 링크