橋口幸三郎

橋口攻三郎（はしぐちこうさぶろう）は、豊橋技術科学大学と岡山大学に在籍する日本の数学者、コンピュータ科学者であり、形式言語理論の研究で知られています。

1988年、橋口は正規言語のスターハイトを決定する最初のアルゴリズムを発見した。この問題は、1963年にローレンス・エガンが関連するスターハイト問題を解き、スターハイトに有限の上限がないことを示して以来、未解決であった。橋口のスターハイトアルゴリズムは非常に複雑で、ごく小さな例を除いて実用的ではない。^[1]^[2]^[H88]より単純な手法は、この問題がPSPACE完全であることを示し、2005年にキルステンによって提供された。^[1]^[3]

橋口は1979年に、正規言語に関する別の未解決問題、すなわち、与えられた言語に対して、となる有限数が存在するかどうかを判断する問題も解いていた。^[4]^[H79] $A$ $n$ $A^{n}=A^{*}$

橋口は日本生まれのアメリカ人ピアニスト、グレース・ニカエの叔父である。^[要出典]

選定された出版物

H79。

橋口幸三郎 (1979). 「規則的イベントの順序を決定する手続き」.理論計算機科学. 8 (1): 69– 72. doi : 10.1016/0304-3975(79)90057-4 . MR 0523661.

H88。

橋口幸三郎 (1988). 「相対的な星高度と星空高度を決定するアルゴリズム」.情報と計算. 78 (2): 124– 169. doi : 10.1016/0890-5401(88)90033-8 . MR 0955580.

参考文献

^ ab Lombardy, Sylvain; Sakarovitch, Jacques (2008). 「ユニバーサル・オートマトン」 Flum, Jörg; Grädel, Erich; Wilke, Thomas (編). Logic and Automata: History and Perspectives . Texts Log. Games. Vol. 2. Amsterdam: Amsterdam Univ. Press. pp. 457– 504. MR 2508751. 特に488ページを参照してください。
^ ピン、ジャン＝エリック (2017). 「35年後の通常言語に関する未解決の問題」。コンスタンティニディス、スタブロスでは。モレイラ、ネルマ。レイス、ロジェリオ。ジェフリー・シャリット（編）。コンピューターサイエンスにおける理論の役割: ヤヌシュ・ブルゾゾフスキーに捧げられたエッセイ。世界科学。ISBN 9789813148215。特に164ページを参照してください。
^ キルステン、ダニエル (2005). 「距離砂漠オートマトンと星の高さ問題」RAIRO 理論情報学および応用. 39 (3): 455– 509. doi :10.1051/ita:2005027. MR 2157045.
^ Brzozowski, Janusz (2014). 「正規言語に関する未解決問題」. ロナルド・V. (編). 『形式言語理論：展望と未解決問題』. アカデミック・プレス. pp. 23– 38. ISBN 9781483267500。特に45ページをご覧ください。

外部リンク

ホームページ

[ls-1] Lombardy, Sylvain; Sakarovitch, Jacques (2008). 「ユニバーサル・オートマトン」 Flum, Jörg; Grädel, Erich; Wilke, Thomas (編). Logic and Automata: History and Perspectives . Texts Log. Games. Vol. 2. Amsterdam: Amsterdam Univ. Press. pp. 457– 504. MR 2508751. 特に488ページを参照してください。

[pin-2] ピン、ジャン＝エリック (2017). 「35年後の通常言語に関する未解決の問題」。コンスタンティニディス、スタブロスでは。モレイラ、ネルマ。レイス、ロジェリオ。ジェフリー・シャリット（編）。コンピューターサイエンスにおける理論の役割: ヤヌシュ・ブルゾゾフスキーに捧げられたエッセイ。世界科学。ISBN 9789813148215。特に164ページを参照してください。

[kirsten-3] キルステン、ダニエル (2005). 「距離砂漠オートマトンと星の高さ問題」RAIRO 理論情報学および応用. 39 (3): 455– 509. doi :10.1051/ita:2005027. MR 2157045.

[brz-4] Brzozowski, Janusz (2014). 「正規言語に関する未解決問題」. ロナルド・V. (編). 『形式言語理論：展望と未解決問題』. アカデミック・プレス. pp. 23– 38. ISBN 9781483267500。特に45ページをご覧ください。