Kosaburo Hashiguchi - Kosaburo Hashiguchi
Kosaburo Hashiguchi (橋 口 攻 三郎, Hashiguchi Kōsaburō) je japonský matematik a počítačový vědec na Toyohashi University of Technology a Okajama univerzita, známý svým výzkumem v formální jazyk teorie.
V roce 1988 našel první algoritmus určit výška hvězdy a běžný jazyk, problém, který byl otevřen od roku 1963, kdy Lawrence Eggan vyřešil související problém s výškou hvězdy ukazovat, že na výšce hvězdy není vázána žádná konečnost. Hashiguchiho algoritmus pro výšku hvězdy je extrémně složitý a nepraktický na všech příkladech kromě těch nejmenších.[1][2][H88] Jednodušší metoda, která také ukazuje, že problém je PSPACE - kompletní, poskytla v roce 2005 společnost Kirsten.[1][3]
Dříve, v roce 1979, Hashiguchi také vyřešil další otevřený problém v běžných jazycích, rozhodování, zda pro daný jazyk , existuje konečné číslo takhle .[4][H79]
Hashiguchi je strýc amerického pianisty narozeného v Japonsku Grace Nikae.[Citace je zapotřebí ]
Vybrané publikace
H79. | Hashiguchi, Kosaburo (1979). "Postup rozhodování o pořadí pravidelných událostí". Teoretická informatika. 8 (1): 69–72. doi:10.1016/0304-3975(79)90057-4. PAN 0523661. |
H88. | Hashiguchi, Kosaburo (1988). Msgstr "Algoritmy pro určení relativní výšky hvězdy a výšky hvězdy". Informace a výpočet. 78 (2): 124–169. doi:10.1016/0890-5401(88)90033-8. PAN 0955580. |
Reference
- ^ A b Lombardy, Sylvain; Sakarovitch, Jacques (2008). "Univerzální automat". In Flum, Jörg; Grädel, Erich; Wilke, Thomas (eds.). Logika a automaty: historie a perspektivy. Protokol textů. Hry. 2. Amsterdam: Amsterdam Univ. Lis. 457–504. PAN 2508751.Viz zejména str. 488.
- ^ Pin, Jean-Éric (2017). "Otevřené problémy s běžnými jazyky, o 35 let později". In Konstantinidis, Stavros; Moreira, Nelma; Reis, Rogério; Shallit, Jeffrey (eds.). Role teorie v informatice: Eseje věnované Januszovi Brzozowskému. World Scientific. ISBN 9789813148215.Viz zejména str. 164.
- ^ Kirsten, Daniel (2005). "Vzdálené pouštní automaty a problém s výškou hvězdy". RAIRO Teoretická informatika a aplikace. 39 (3): 455–509. doi:10.1051 / ita: 2005027. PAN 2157045.
- ^ Brzozowski, Janusz (2014). Msgstr "Otevřené problémy s běžnými jazyky". V knize Ronald V. (ed.). Teorie formálního jazyka: Perspektivy a otevřené problémy. Akademický tisk. 23–38. ISBN 9781483267500.Viz zejména str. 45.