Janusz (Juan) Antoni Brzozowski (10 mayo 1935 a 24 octubre 2019) era un polaco-canadiense científico de la computación y distinguido profesor emérito [1] en la Universidad de Waterloo 's David R. Facultad de Ciencias de la Computación Cheriton . [2]
Janusz Brzozowski | |
---|---|
Nació | |
Fallecido | 24 de octubre de 2019 Casa Lisaard , Cambridge, Ontario , Canadá | (84 años)
alma mater | Universidad de Princeton |
Conocido por | Derivado de Brzozowski |
Carrera científica | |
Campos | Ciencias de la Computación |
Tesis | Técnicas de expresión regular para circuitos secuenciales (1962) |
Asesor de doctorado | Edward J. McCluskey |
En 1962, Brzozowski obtuvo su doctorado en el campo de la ingeniería eléctrica en la Universidad de Princeton con Edward J. McCluskey . El tema de la tesis fue Técnicas de expresión regular para circuitos secuenciales . De 1967 a 1996 fue profesor en la Universidad de Waterloo . Es conocido por sus contribuciones a la lógica matemática , la teoría de circuitos y la teoría de autómatas .
Logros en investigación
Brzozowski trabajó en expresiones regulares y en semigrupos sintácticos de lenguajes formales . [3] El resultado fueron caracterizaciones de eventos comprobables localmente escritos junto con Imre Simon , que tuvieron un impacto similar [4] en el desarrollo de la teoría algebraica de lenguajes formales como la caracterización de Marcel-Paul Schützenberger de los lenguajes libres de estrellas .
En el área, hoy al menos tres conceptos llevan el nombre de Brzozowski en honor a sus contribuciones: El primero es la conjetura de Brzozowski [5] sobre la regularidad de las clases no contables. En segundo lugar, el algoritmo de Brzozowski [6], un algoritmo conceptualmente simple para realizar la minimización de DFA . En tercer lugar, el trabajo de referencia de Eilenberg sobre la teoría de los autómatas tiene un capítulo dedicado a la llamada jerarquía de Brzozowski [7] dentro de los lenguajes libres de estrellas , también conocida como jerarquía de profundidad de puntos . Curiosamente, Brzozowski no solo fue coautor del artículo que definió la jerarquía de profundidad de puntos y planteó la cuestión de si esta jerarquía es estricta, [8] más tarde también fue coautor del artículo que resolvió ese problema después de aproximadamente diez años. [9] La jerarquía de Brzozowski ganó mayor importancia después de que Thomas descubrió una relación entre el concepto algebraico de profundidad de punto y la profundidad de alternancia de cuantificadores en la lógica de primer orden a través de los juegos de Ehrenfeucht-Fraïssé . [10]
Ha recibido los siguientes premios y distinciones académicas:
- Premio NSERC Scientific Exchange a Francia (1974-1975)
- Beca de investigación de la Sociedad Japonesa para la Promoción de la Ciencia (1984)
- Certificado de reconocimiento de la Asociación de Investigación en Computación por contribuciones sobresalientes y servicio como miembro de la Junta Directiva de la CRA (1992)
- Profesor emérito distinguido, Universidad de Waterloo , Canadá (1996) [11]
- Medalla al Mérito, Universidad Católica de Lublin, Polonia (2001)
- IBM Canada Canadian Pioneer in Computing (2005) [12]
- The Role of Theory in Computer Science, una conferencia de un día en honor al 80 cumpleaños de John Brzozowski (2015) [13]
- Premio a la Trayectoria, Computer Science Canada / Informatique Canada (CS-CAN / INFO-CAN) (2016) [14]
- Premio Sheng Yu de la CIAA 2017 al mejor artículo por la complejidad de los lenguajes regulares convexos de prefijos adecuados por J. Brzozowski y C. Sinnamon [15]
- Premio Sheng Yu de la CIAA 2018 al mejor artículo por la complejidad del estado del ensamblaje de superposición por J. Brzozowski, L. Kar i, B. Li, M. Szykula [16]
Trabajos de investigación
- JA Brzozowski: Derivadas de expresiones regulares, Journal of the ACM 11 (4): 481–494 (1964)
- JA Brzozowski, I. Simon: Caracterizaciones de eventos comprobables localmente, FOCS 1971, págs. 166-176
- RS Cohen, JA Brzozowski: Puntos de profundidad de eventos sin estrellas. Revista de Ciencias de la Computación y Sistemas 5 (1): 1-16 (1971)
- JA Brzozowski, R. Knast: La jerarquía de profundidad de puntos de los lenguajes sin estrellas es infinita. Revista de Ciencias de la Computación y Sistemas 16 (1): 37–55 (1978)
Libros
- JA Brzozowski, M. Yoeli: Redes digitales. Prentice – Hall, 1976
- JA Brzozowski, C.-JH Seger: Circuitos asincrónicos. Springer-Verlag, 1995
Notas
- ^ "John Brzozowski" . Escuela de Ciencias de la Computación David R. Cheriton . Consultado el 21 de diciembre de 2018 .
- ^ https://www.legacy.com/obituaries/theglobeandmail/obituary.aspx?n=janusz-a-brzozowski&pid=194286993&fhid=30885
- ↑ Pin (1997)
- ^ Diekert y col. (2008)
- ↑ de Luca y Varicchio (1997)
- ↑ Shallit (2009), cap. 3.10
- ^ Eilenberg (1974)
- ^ Cohen y Brzozowski (1971)
- ^ Brzozowski y Knast (1979)
- ↑ Thomas (1982)
- ^ Perfil de John Brzozowski
- ^ Pioneros de la informática en Canadá, 2005, http://individual.utoronto.ca/klyons/files/pioneers.pdf Consultado el 2 de enero de 2019.
- ^ "Brzozowski 80: el papel de la teoría en la informática" . Escuela de Ciencias de la Computación David R. Cheriton . 24 de junio de 2015 . Consultado el 21 de diciembre de 2018 .
- ^ "Premios a la Trayectoria | 2016" . Computer Science Canada / Information Canada (CS-CAN / INFO-CAN) . 2016 . Consultado el 21 de diciembre de 2018 .
- ^ "Implementación y aplicación de la 22ª Conferencia Internacional de Autómatas | Premio Sheng Yu 2017" . Conferencia sobre Implementación y Aplicación de Autómatas (CIAA 2017) . 2017 . Consultado el 21 de diciembre de 2018 .
- ^ "23ª Conferencia Internacional sobre Implementación y Aplicaciones de Autómatas | Premio Sheng Yu 2018" . 23a Conferencia Internacional sobre Implementación y Aplicaciones de Autómatas (CIAA 2018) . 23 de agosto de 2018 . Consultado el 21 de diciembre de 2018 .
Referencias
- S. Eilenberg, Autómatas, lenguajes y máquinas , volumen B. ISBN 0-12-234001-9
- W. Thomas, Clasificación de eventos regulares en lógica simbólica. J. Comput. Syst. Sci. 25 (3): 360-376 (1982)
- J.-E. Pin, semigrupos sintácticos , capítulo 10 en "Manual de teoría del lenguaje formal", vol. 1, G. Rozenberg y A. Salomaa (eds.), Springer Verlag, (1997) vol. 1, págs. 679–746
- A. de Luca y S. Varicchio, Condiciones de regularidad y finitud , Capítulo 11 en "Manual de teoría del lenguaje formal", Vol. 1, G. Rozenberg y A. Salomaa (eds.), Springer Verlag, (1997) vol. 1, págs. 747–810
- V. Diekert, P. Gastin, M. Kufleitner, Una encuesta sobre pequeños fragmentos de lógica de primer orden sobre palabras finitas. En t. J. Encontrado. Computación. Sci. 19 (3): 513-548 (2008)
- J. Shallit, Un segundo curso en lenguajes formales y teoría de los autómatas , Cambridge University Press (2009)
enlaces externos
- Perfil de Janusz Brzozowski, Universidad de Waterloo
- Sitio web personal de Brzozowski en la Universidad de Waterloo
- Salón de la Fama de la Teoría de la Computación
- Janusz A. Brzozowski en el servidor de bibliografía DBLP
- Jerarquías de concatenación por Jean-Eric Pin