Résumé : Ce dialogue entre Quisani, l'étudiant
imaginaire de Yuri Gurevich, et l'auteur, a été publié
dans la "Logic in Computer Science Column" du Bulletin de l'EATCS. Il
s'adresse en priorité à des logiciens. On y
présente, au fil du dialogue, les relations entre le calcul
séquentiel de Büchi et la théorie des automates finis.
On discute en particulier du rôle central des formules du premier
ordre et des hiérarchies de quantifications sur ces formules, qui
débouchent sur des problèmes ouverts.
Abstract : This dialog between Quisani, Yuri Gurevich's imaginary
student, and the author, was published in the "Logic in Computer Science
Column" of the EATCS Bulletin. It is first addressed to logicians. This
dialog is an occasion to present the connections between Büchi's
sequential calculus and the theory of finite automata. In particular, the
essential role of first order formulæ is emphasized. The quantifier
hierarchies on these formulæ are an occasion to present open
problems.
PostScript file compressed
with gzip, PDF
file
