Jean Henri Gallier (nacido en 1949) es un investigador en lógica computacional en la Universidad de Pensilvania , donde ocupa puestos en el Departamento de Ciencias de la Computación y la Información y en el Departamento de Matemáticas.
Gallier nació el 5 de enero de 1949 en Nancy, Francia , y posee doble ciudadanía francesa y estadounidense. Obtuvo su bachillerato en el Lycée de Sèvres en 1966, y una licenciatura en ingeniería civil en la École Nationale des Ponts et Chaussées en 1972. [1] Luego se trasladó a la Universidad de California en Los Ángeles para sus estudios de posgrado, obteniendo un doctorado en informática en 1978 bajo la supervisión conjunta de Sheila Greibach y Emily Perlinski Friedman. Su disertación se tituló Semántica y corrección de clases de programas recursivos deterministas y no deterministas . [1] [2] Después de realizar estudios postdoctorales en la Universidad de California, Santa Bárbara , se unió al Departamento de Informática y Ciencias de la Información de la Universidad de Pensilvania en 1978. En Pensilvania, fue ascendido a profesor titular en 1990, obtuvo un nombramiento secundario en el Departamento de Matemáticas en 1994 y dirigió el Instituto Francés de Cultura y Tecnología de 2001 a 2004. [1]
El trabajo de investigación más citado de Gallier, con su alumno William F. Dowling, ofrece un algoritmo de tiempo lineal para la satisfacibilidad de Horn . [DG84] Esta es una variante del problema de satisfacibilidad booleano : su entrada es una fórmula booleana en forma normal conjuntiva con como máximo un literal positivo por cláusula, y el objetivo es asignar valores de verdad a las variables de la fórmula para hacer que toda la fórmula sea verdadera. La resolución de problemas de satisfacibilidad de Horn es el paradigma computacional central en el lenguaje de programación Prolog . [3]
Gallier es también autor de cinco libros sobre lógica computacional, [G86] geometría computacional , [G99] [G00] topología de baja dimensión , [GX13] y matemáticas discretas . [G11]