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 In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity
of regular expressions and regular languages. The star height of a regular ''expression'' equals the maxim ...
of a
regular language, a problem that had been open since 1963 when Lawrence Eggan solved the related
star height problem
The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth ...
, 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. A simpler method, showing also that the problem is
PSPACE-complete, was provided in 2005 by Kirsten.
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
.
Hashiguchi is the uncle of Japanese-born American pianist
Grace Nikae
Grace Nikae (born in Kagoshima, Japan) is an American classical pianist. At the age of 3 months, she moved to Honolulu, Hawaii and grew up in Aiea. She was raised by her mother, Kazuko Hashiguchi, who is a teacher.Moniz, Melissa: "Born to Play the ...
.
Selected publications
References
External links
Home page
{{DEFAULTSORT:Hashiguchi, Kosaburo
Year of birth missing (living people)
Living people
Japanese mathematicians
Japanese computer scientists
Theoretical computer scientists