# Seymour Ginsburg

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

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. 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 ».
Ginsburg occupe de 1951 à 1955 un poste de professeur assistant en mathématiques à l'université de Miami en Floride. 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é du Sud de la Californie. 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

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.
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'appelait alors les langages « ALGOL-like » languages. 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. 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. De nombreux travaux de cette époque sont é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.
L'unification des divers aspects des systèmes formels a été un thème constant chez Ginsburg. 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. L'ensemble de la théorie est exposé dans le livre Algebraic and automata theoretic properties of formal languages paru en 1975. 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éée.
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.

## Livres

Gisnburg est auteur de nombreux articles, et de trois livres :
* Seymour Ginsburg, Introduction to Mathematical Machine Theory, Addison Wesley, 1962.
* Seymour Ginsburg, The Mathematical Theory of Context-free Languages, New York, McGraw-Hill, 1966.
* Seymour Ginsburg, Algebraic and Automata Theoretic Properties of Formal Languages, North-Holland, 1975, xii+313 (ISBN 0-7204-2506-9)