Kosaburo Hashiguchi
Kosaburo Hashiguchi (橋口 攻三郎, Hashiguchi Kōsaburō ) es un matemático e informático japonés de la Universidad Tecnológica de Toyohashi y la Universidad de Okayama , conocido por su investigación en la teoría del lenguaje formal .
En 1988, encontró el primer algoritmo para determinar la altura de la estrella de un lenguaje regular , un problema que había estado abierto desde 1963 cuando Lawrence Eggan resolvió el problema relacionado con la altura de la estrella de mostrar que no hay un límite finito en la altura de la estrella. El algoritmo de Hashiguchi para la altura de las estrellas es extremadamente complejo y poco práctico en todos los ejemplos, excepto en los más pequeños. [1] [2] [H88] Kirsten proporcionó en 2005 un método más simple, que muestra también que el problema es PSPACE-completo . [1] [3]
Anteriormente, en 1979, Hashiguchi también había resuelto otro problema abierto sobre los lenguajes regulares, de decidir si, para un idioma dado , existe un número finito tal que . [4] [H79]
