Джованни Пигиццини

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

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

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

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

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

Ссылки

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

Внешние ссылки

Официальный сайт
Джованни Пигиццини на DBLP библиографическом сервере

[MereghettiPighizzini2001-1] Мерегетти, Карло; Пигиццини, Джованни (2001). «Оптимальное моделирование унарных автоматов». SIAM Journal по вычислительной технике . 30 (6): 1976–1992. дои : 10.1137/S009753979935431X . hdl : 2434/35121 . ISSN 0097-5397 .

[GeffertMereghetti2003-2] Jump up to: ^а ^б Гефферт, Вильям; Мерегетти, Карло; Пигиццини, Джованни (2003). «Преобразование двусторонних недетерминированных унарных автоматов в более простые автоматы». Теоретическая информатика . 295 (1–3): 189–203. дои : 10.1016/S0304-3975(02)00403-6 . ISSN 0304-3975 .

[GeffertGuillon2014-3] Гефферт, Уильям; Гийон, Бруно; Пигидзини, Джованни (2014). «Двусторонние автоматы, делающие выбор только на конечных маркерах». Информация и вычисления . 239 : 71–86. arXiv : 1110.1263 . дои : 10.1016/j.ic.2014.08.009 . ISSN 0890-5401 .

[JiráskováPighizzini2011-4] Йираскова, Галина; Пигиццини, Джованни (2011). «Оптимальное моделирование самопроверяющихся автоматов детерминированными автоматами». Информация и вычисления . 209 (3): 528–535. дои : 10.1016/j.ic.2010.11.017 . ISSN 0890-5401 .

[GeffertMereghetti1998-5] Гефферт, Вильям; Мерегетти, Карло; Пигиццини, Джованни (1998). «Сублогарифмические границы пространства и развороты». SIAM Journal по вычислительной технике . 28 (1): 325–340. дои : 10.1137/S0097539796301306 . hdl : 2434/178756 . ISSN 0097-5397 . S2CID 37853723 .

[AllenderBruschi1993-6] Аллендер, Эрик; Бруски, Данило; Пигиццини, Джованни (1993). «Сложность вычисления максимальных словесных функций». Вычислительная сложность . 3 (4): 368–391. дои : 10.1007/BF01275489 . ISSN 1016-3328 . S2CID 886700 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

Базы данных авторитетного контроля
Международный	ВИАФ WorldCat
Национальный	Германия Италия Израиль Соединенные Штаты
академики	Ассоциация вычислительной техники ДБЛП Google Академика MathSciNet ОРЦИД Скопус zbMATH
Другой	ИдРеф