Kosaburo Hashiguchi
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
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.
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, 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.[citation needed]
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.
|
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.