Imre Simon
Imre Simon (* 14. August 1943 in Budapest; † 13. August 2009 in São Paulo) war ein brasilianischer Informatiker und Mathematiker.
Simon kam mit seinen Eltern nach dem Ungarischen Aufstand 1957 nach Brasilien. Er studierte Elektrotechnik in Sao Paulo (bei Tomasz Kowaltowski) und erhielt 1970 sein Diplom und wurde 1972 an der University of Waterloo bei Janusz Brozozowski promoviert (Hierarchies of Events with Dot-Depth One)[1]. Ab 1984 war er Professor an der Universität São Paulo und ging dort 2002 in den Ruhestand. 1994 bis 1998 war er Präsident des Zentralkomitees für Informatik der Universität Sao Paulo.
Simon leistete Beiträge zur Automatentheorie und gilt als Pionier der theoretischen Informatik in Brasilien und Begründer der Tropischen Geometrie (eine Bezeichnung die ihren Ursprung in der brasilianischen Herkunft von Simon hat). Er verbesserte den Knuth-Morris-Pratt-Algorithmus, schuf eine effektive Charakterisierung lokal testbarer Sprachen und führte nichtdeterministische Komplexität von Automaten und Faktorisierungs-Wälder (factorization forests) ein. Nach ihm ist die Simon-Kongruenz benannt (zwischen Wörtern mit denselben Teilwörtern bis zur Länge n). Simon war ein Befürworter freier Software.
2006 gewann er den Preis für wissenschaftliche Verdienste der brasilianischen Gesellschaft für Informatik, 1979 den Jabuti-Preis für exakte Wissenschaften und 1989 den Wissenschaftspreis der Union des Assurances de Paris (UAP) mit Michail Leonidowitsch Gromow und Joseph Stiglitz. Er war Mitglied der Brasilianischen Akademie der Wissenschaften und erhielt das Großkreuz des Ordem Nacional do Mérito Científico. Simon war auch Präsident der brasilianischen mathematischen Gesellschaft.
Schriften
- mit Cláudio L. Lucchesi, Istvan Simon, Janos Simon, Tomasz Kowaltowski: Aspectos Teóricos da Computação, Projeto Euclides, IMPA, 1979.
- On the time required by the Davis-Putnam tautology recognition algorithm., Notices Amer. Math. Soc., Band 18, 1971, S. 970.
- mit Janusz A. Brzozowski: Characterizations of locally testable events, Discrete Mathematics, Band 4, 1973, S. 243–271
- Limited subsets of a free monoid, in: Proceedings of the 19th Annual Symposium on Foundations of Computer Science, IEEE, 1978
- Recognizable sets with multiplicities in the tropical semiring, in: M.P. Chytil, L. Janiga, V. Koubek (Hrsg.), Mathematical Foundations of Computer Science, Karlsbad 1988, Lecture Notes in Computer Science 324, Springer Verlag, S. 107–120.
- Properties of factorization forests, in: Jean-Eric Pin (Hrsg.), Formal Properties of Finite Automata and Applications, Springer-Verlag, Lecture Notes in Computer Science, 386, 1989, S. 65–72.
- The nondeterministic complexity of a finite automaton, in: M. Lothaire (Hrsg.), Mots - mélanges offerts à M.P. Schützenberger, Hermes, Paris, 1990, S. 384–400.
- String matching algorithms and automata, in: H. Maurer J. Karhumäki, G. Rozenberg (Hrsg.), Results and Trends in Theoretical Computer Science, Colloquium in Honor of Arto Salomaa, Lecture Notes in Computer Science 812, Springer Verlag 1994, S. 386–395.