Джованни Пигиццини - Giovanni Pighizzini

Джованни Пигиццини
Альма-матерМиланский университет
Известенсложность состояния
Научная карьера
ПоляТеоретическая информатика
формальная теория языка
УчрежденияМиланский университет

Джованни Пигиццини является Итальянский теоретик-информатик известен своей работой в формальная теория языка и особенно в сложность состояния из двусторонние конечные автоматы. Он получил докторскую степень в 1993 г. Миланский университет, где он является профессором с 2001 года. Пигиццини является председателем Руководящего комитета ежегодного Описание сложности формальных систем научная конференция с 2006 года.

Вклад в исследования

Пигиццини получил оптимальное сложность состояния компромиссы между различными типами конечные автоматы над однобуквенным алфавитом,[1][2][3] В частности, в его совместной работе с Гефферт и Мегетти[2] он представил первую симуляцию двусторонние недетерминированные конечные автоматы к двусторонние детерминированные конечные автоматы с помощью Теорема савича, способствуя 2DFA против 2NFA открытый вопрос. Совместно с Йирасковой он определил сложность состояния из самопроверяющиеся конечные автоматы.[4]

Он также внес свой вклад в теория сложности вычислений по результатам о классах сложности сублогарифмических пространств[5] и от сложности поиска лексикографически максимальной строки.[6]

Рекомендации

  1. ^ Мегетти, Карло; Пигиццини, Джованни (2001). «Оптимальное моделирование между унарными автоматами». SIAM Журнал по вычислениям. 30 (6): 1976–1992. Дои:10.1137 / S009753979935431X. HDL:2434/35121. ISSN  0097-5397.
  2. ^ а б Гефферт, Вильям; Мегетти, Карло; Пигиццини, Джованни (2003). «Преобразование двусторонних недетерминированных унарных автоматов в более простые автоматы». Теоретическая информатика. 295 (1–3): 189–203. Дои:10.1016 / S0304-3975 (02) 00403-6. ISSN  0304-3975.
  3. ^ Гефферт, Вильям; Гийон, Бруно; Пигиццини, Джованни (2014). «Двусторонние автоматы, делающие выбор только на крайних точках». Информация и вычисления. 239: 71–86. arXiv:1110.1263. Дои:10.1016 / j.ic.2014.08.009. ISSN  0890-5401.
  4. ^ Йираскова, Галина; Пигиццини, Джованни (2011). «Оптимальное моделирование самопроверяющихся автоматов детерминированными автоматами». Информация и вычисления. 209 (3): 528–535. Дои:10.1016 / j.ic.2010.11.017. ISSN  0890-5401.
  5. ^ Гефферт, Вильям; Мегетти, Карло; Пигиццини, Джованни (1998). «Сублогарифмические границы пространства и инверсии». SIAM Журнал по вычислениям. 28 (1): 325–340. Дои:10.1137 / S0097539796301306. HDL:2434/178756. ISSN  0097-5397.
  6. ^ Аллендер, Эрик; Бруски, Данило; Пигиццини, Джованни (1993). «Сложность вычисления максимальных функций слова». Вычислительная сложность. 3 (4): 368–391. Дои:10.1007 / BF01275489. ISSN  1016-3328.

внешняя ссылка