Seymour Ginsburg

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Seymour Ginsburg
Naissance
Philadelphie, PA, États-Unis
Décès
Domaines Informatique théorique, théorie des langages, théorie des bases de données
Institutions Université de Californie du Sud, Université de Miami
Diplôme Ph. D.
Formation City College of New York, Université du Michigan
Directeur de thèse Ben Dushnik
Étudiants en thèse Serge Abiteboul, William Chandler, Timothy Connors, Guozhu Dong, Joseph Giuliano, Donald Kiel, Stephen Kurtzman, George Mager, Gary Miles, David Mizell, Branislav Rovan, Dan Tian, Victor Vianu, X. Sean Wang, Sami Zaiddan[1]
Renommé pour Langage formel, Famille abstraite de langages, Théorie des bases de données theory

Seymour Ginsburg, né le 12 décembre 1927 et mort le 5 décembre 2004, est un informaticien théoricien américain, pionnier de la théorie des automates, des langages formels et notamment des langages algébriques, et de la théorie des bases de données. Son influence historique est importante dans le développement d'une informatique théorique en tant que discipline à part entière, distincte du génie électrique.

Biographie scientifique[modifier | modifier le code]

Seymour Ginsburg obtient un B. Sc. au City College of New York en 1948, où il a assisté, en même temps que Martin Davis, à un cours avancé (« honors class ») donné par Emil Post[2]. Il obtient un Ph. D. en mathématiques à l'université du Michigan en 1953, sous la direction de Ben Dushnik, avec une thèse intitulée « Order Types and Similarity Transformations »[1].

Ginsburg occupe de 1951 à 1955 un poste de professeur assistant en mathématiques à l'université de Miami en Florida. Ses intérêts se portent sur l’Informatique lorsqu'il rejoint, en 1955, la Northrop Corporation en Californie . Il occupe ensuite des emplois à NCR Corporation, Hughes Aircraft, et System Development Corporation (en) (SDC). En 1966, il devient professeur titulaire à l'Université de Californie du Sud. Ginsburg est nommé Fletcher Jones Professor of Computer Science à l'Université de Californie du Sud en 1978, chaire qu'il occupe jusqu'à sa retraite en 1999. À cette date, on lui diagnostique la maladie d'Alzheimer. Il cesse d'enseigner, et devient professeur émérite en informatique.

Travaux de recherche[modifier | modifier le code]

Encore à SDC, Ginsburg travaille d'abord sur la théorie des machines abstraites. Les premières contributions de Ginsburg concernent la theory des automates finis, entre autres la minimisation. Ses travaux donnent naissance à un premier livre : Introduction to Mathematical Machine Theory en 1962[3].

Il se consacre ensuite à la théorie des langages formels. Il étudie les grammaires context-free et les langages context-free. Ginsburg observe qu'il y a une connexion entre les langages algébriques et ce qui s'appellait alors les langages « ALGOL-like » languages[4]. Les résultats de Ginsburg et de ses coauteurs sur les langages déterministes, les langages bornés, les propriétés de décision sont considérés comme faisant partie des résultats les plus importants et les plus profonds de la théorie[5]. Le groupe de chercheurs qu'il constitue comporte notamment Sheila Greibach, Michael A. Harrison, Gene Rose, Edwin Spanier et Joe Ullian. Ginsburg occupe dans ce groupe, mais plus généralement en informatique théorique à l’époque un rôle dirigeant. À la recherche en la théorie des langages non contextuels « context-free languages » participent entre autres Jonathan Goldstine, Harrison, John Hopcroft, Spanier[5]. De nombreux travaux de cette époque son écrits en collaboration avec ces chercheurs.

Son livre The Mathematical Theory of Context-free Languages paraît en 1966. Il est pendant très longtemps un livre de référence sur la théorie des langages algébriques[6].

L'unification des divers aspects des systèmes formels a été un thème constant chez Ginsburg[5]. En théorie des langages formels, ses articles dans cette direction portent sur le lien entre systèmes de grammaires, systèmes d'accepteurs, et caractérisation algébrique des familles de langages. Il en est résulté le concept de famille abstraite de langages, dont la première mention apparaît dans un article commun avec Sheila Greibach en 1967[7]. L'ensemble de la théorie est exposé dans le livre Algebraic and automata theoretic properties of formal languages paru en 1975[8]. Dans le même esprit, Ginsburg développe, avec Armin B. Cremers (en) la théorie des « grammar forms ».

Ginsburg obtient une Bourse Guggenheim en 1974 et en profite pour faire des conférences un peu partout dans le monde sur la théorie qu'il a créé.

Au début des années 1980, Ginsburg change de thème de recherche : il s'oriente vers les bases de données. Il devient un pionnier dans le domaine de la théorie des bases de données, domaine dans lequel il travaille jusqu'à sa retraite. Il assemble autour de lui un groupe de chercheurs sur cette théorie. Ses contributions concernent la dépendance fonctionnelle, des histoires d'objets, histoires de tableurs spreadsheet, Datalog, et restructuration de données. En 1982, il organise la première conférence PODS (Symposium on Principles of Database Systems (en)) à Marina del Rey. En 1992, une session spéciale de la conférence était dévolue à fêter le 64e anniversaire avec une Festschrift éditée par Jeffrey Ullman[9].

Livres[modifier | modifier le code]

Gisnburg est auteur de nombreux articles, et de trois livres :

  • Seymour Ginsburg, Introduction to Mathematical Machine Theory, Addison Wesley, .
  • Seymour Ginsburg, The Mathematical Theory of Context-free Languages, New York, McGraw-Hill, .
  • Seymour Ginsburg, Algebraic and Automata Theoretic Properties of Formal Languages, North-Holland, , xii+313 p. (ISBN 0-7204-2506-9)

Notes et références[modifier | modifier le code]

  1. a et b (en) Seymour Ginsburg sur le site du Mathematics Genealogy Project.
  2. Alasdair Urquhart, « Emil Post : Logic from Russell to Church », dans Dov M. Gabbay et John Woods, Handbook of the History of Logic, vol. 5, North Holland, (ISBN 978-0-444-51620-6), p. 659.
  3. Ginsburg 1962.
  4. Seymour Ginsburg et H. Gordon Rice, « Two Families of Languages Related to ALGOL », Journal of the ACM, vol. 9, no 3,‎ , p. 350–371 (DOI 10.1145/321127.321132).
  5. a, b et c Serge Abiteboul, Richard Hull et Victor Vianu, « In memory of Seymour Ginsburg, 1928-2004 », ACM SIGMOD Record, vol. 34, no 1,‎ , p. 5-12 (DOI 10.1145/1058150.1058152)
  6. Ginsburg 1966.
  7. Seymour Ginsburg et Sheila A. Greibach, « Abstract Families of Languages », 8th Annual Symposium on Switching and Automata Theory, Austin, Texas, IEEE Computer Society,‎ , p. 128–139.
  8. Ginsburg 1975.
  9. Jeff Ullman, To Seymour Ginsburg on the occasion of his birthday, Academic Press, coll. « Theoretical Studies in Computer Science », (ISBN 0-12-708240-9)

Liens externes[modifier | modifier le code]