Косабуро Хасигути

Косабуро Хасигути ( 橋口攻三郎 , Хасигути Косабуро ) — японский математик и ученый-компьютерщик из Технологического университета Тоёхаси и Университета Окаяма , известный своими исследованиями в области формального языка теории .

В 1988 году он нашел первый алгоритм определения высоты звезды в регулярном языке — проблема, которая была открыта с 1963 года, когда Лоуренс Эгган решил связанную с ней проблему высоты звезды , показав, что не существует конечной границы высоты звезды.Алгоритм Хасигути для определения высоты звезды чрезвычайно сложен и непрактичен для всех примеров, кроме самых маленьких. ^[1]^[2]^[Н88] Более простой метод, показывающий также, что проблема является PSPACE-полной , был предложен в 2005 году Кирстен. ^[1]^[3]

Ранее, в 1979 году, Хасигути также решил еще одну открытую проблему регулярных языков: решить, является ли для данного языка $A$ , существует конечное число $n$ такой, что $A^{n}=A^{*}$ . ^[4]^[H79]

Хасигути — дядя американской пианистки японского происхождения Грейс Никаэ . ^{[ нужна ссылка ]}

Избранные публикации

Х79.

Хасигути, Косабуро (1979). «Порядок принятия решения о порядке проведения регулярных мероприятий» . Теоретическая информатика . 8 (1): 69–72. дои : 10.1016/0304-3975(79)90057-4 . МР 0523661 .

Х88.

Хасигути, Косабуро (1988). «Алгоритмы определения относительной высоты звезды и высоты звезды» . Информация и вычисления . 78 (2): 124–169. дои : 10.1016/0890-5401(88)90033-8 . МР 0955580 .

Ссылки

^ Перейти обратно: ^а ^б Ломбардия, Сильвен; Сакарович, Жак (2008). «Универсальный автомат». Во Флуме, Йорг; Гредель, Эрих; Уилке, Томас (ред.). Логика и автоматы: история и перспективы . Журнал текстов. Игры. Том. 2. Амстердам: Амстердамский унив. Нажимать. стр. 457–504. МР 2508751 . См., в частности, стр. 488 .
^ Пин, Жан-Эрик (2017). «Открытые проблемы обычных языков, 35 лет спустя». В Константинидис, Ставрос; Морейра, Нельма; Рейс, Рожерио; Шалит, Джеффри (ред.). Роль теории в информатике: очерки, посвященные Янушу Бжозовскому . Всемирная научная. ISBN 9789813148215 . См., в частности, стр. 164 .
^ Кирстен, Дэниел (2005). «Дальние пустынные автоматы и проблема высоты звезды» . РАЙРО Теоретическая информатика и приложения . 39 (3): 455–509. дои : 10.1051/ita:2005027 . МР 2157045 .
^ Бжозовский, Януш (2014). «Открытые проблемы о регулярных языках». В книге Рональда В. (ред.). Теория формального языка: перспективы и открытые проблемы . Академическая пресса. стр. 23–38. ISBN 9781483267500 . См., в частности, стр. 45 .

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

Домашняя страница

[ls-1] Перейти обратно: ^а ^б Ломбардия, Сильвен; Сакарович, Жак (2008). «Универсальный автомат». Во Флуме, Йорг; Гредель, Эрих; Уилке, Томас (ред.). Логика и автоматы: история и перспективы . Журнал текстов. Игры. Том. 2. Амстердам: Амстердамский унив. Нажимать. стр. 457–504. МР 2508751 . См., в частности, стр. 488 .

[pin-2] Пин, Жан-Эрик (2017). «Открытые проблемы обычных языков, 35 лет спустя». В Константинидис, Ставрос; Морейра, Нельма; Рейс, Рожерио; Шалит, Джеффри (ред.). Роль теории в информатике: очерки, посвященные Янушу Бжозовскому . Всемирная научная. ISBN 9789813148215 . См., в частности, стр. 164 .

[kirsten-3] Кирстен, Дэниел (2005). «Дальние пустынные автоматы и проблема высоты звезды» . РАЙРО Теоретическая информатика и приложения . 39 (3): 455–509. дои : 10.1051/ita:2005027 . МР 2157045 .

[brz-4] Бжозовский, Януш (2014). «Открытые проблемы о регулярных языках». В книге Рональда В. (ред.). Теория формального языка: перспективы и открытые проблемы . Академическая пресса. стр. 23–38. ISBN 9781483267500 . См., в частности, стр. 45 .

[1]

[2]

[3]

[4]