Косабуро Хасигучи - Kosaburo Hashiguchi

Родная форма этого личное имя является Хасигучи Косабуро. В этой статье используется Западный порядок имен при упоминании лиц.

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

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

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

Хасигучи - дядя американского пианиста японского происхождения. Грейс Никаэ.[нужна цитата ]

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

H79.Хасигучи, Косабуро (1979). «Порядок принятия решения о порядке проведения регулярных мероприятий». Теоретическая информатика. 8 (1): 69–72. Дои:10.1016/0304-3975(79)90057-4. МИСТЕР  0523661.
H88.Хасигути, Косабуро (1988). «Алгоритмы определения относительной высоты звезды и высоты звезды». Информация и вычисления. 78 (2): 124–169. Дои:10.1016/0890-5401(88)90033-8. МИСТЕР  0955580.

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

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

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