Kosaburo Hashiguchi

Kosaburo Hashiguchi (橋口 攻三郎, Hashiguchi Kōsaburō) is a Japanese mathematician and computer scientist at the Toyohashi University of Technology and Okayama University, known for his research in formal language theory.

The native form of this personal name is Hashiguchi Kosaburo. This article uses Western name order when mentioning individuals.

In 1988, he found the first algorithm to determine the star height of a regular language, a problem that had been open since 1963 when Lawrence Eggan solved the related star height problem of showing that there is no finite bound on the star height. Hashiguchi's algorithm for star height is extremely complex, and impractical on all but the smallest examples.[1][2][H88] A simpler method, showing also that the problem is PSPACE-complete, was provided in 2005 by Kirsten.[1][3]

Earlier, in 1979, Hashiguchi had also solved another open problem on regular languages, of deciding whether, for a given language , there exists a finite number such that .[4][H79]

Hashiguchi is the uncle of Japanese-born American pianist Grace Nikae.

Selected publications
H79.Hashiguchi, Kosaburo (1979). "A decision procedure for the order of regular events". Theoretical Computer Science. 8 (1): 69–72. doi:10.1016/0304-3975(79)90057-4. MR 0523661.
H88.Hashiguchi, Kosaburo (1988). "Algorithms for determining relative star height and star height". Information and Computation. 78 (2): 124–169. doi:10.1016/0890-5401(88)90033-8. MR 0955580.
gollark: While it *did* leave the Buisness space station due to conflicts with management, it did not go out of *business* ever.
gollark: Due to the ongoing Lambda Incident their results were not independently reproduced for several [REDACTED], see.
gollark: Actually, Dwight-Helventica were paid by GTech™ to report inaccurate observations to retroactively influence Tux1 counter-optical-phased-array system designs.
gollark: This was disproven by the Lopez-Monroe experiment of 2███3 actually.
gollark: #9 seems to be forking a bunch of "apiary" servers for sorting somehow.

References
  1. Lombardy, Sylvain; Sakarovitch, Jacques (2008). "The universal automaton". In Flum, Jörg; Grädel, Erich; Wilke, Thomas (eds.). Logic and Automata: History and Perspectives. Texts Log. Games. 2. Amsterdam: Amsterdam Univ. Press. pp. 457–504. MR 2508751. See in particular p. 488.
  2. Pin, Jean-Éric (2017). "Open problems about regular languages, 35 years later". In Konstantinidis, Stavros; Moreira, Nelma; Reis, Rogério; Shallit, Jeffrey (eds.). The Role Of Theory In Computer Science: Essays Dedicated To Janusz Brzozowski. World Scientific. ISBN 9789813148215. See in particular p. 164.
  3. Kirsten, Daniel (2005). "Distance desert automata and the star height problem". RAIRO Theoretical Informatics and Applications. 39 (3): 455–509. doi:10.1051/ita:2005027. MR 2157045.
  4. Brzozowski, Janusz (2014). "Open problems about regular languages". In Book, Ronald V. (ed.). Formal Language Theory: Perspectives and Open Problems. Academic Press. pp. 23–38. ISBN 9781483267500. See in particular p. 45.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.