Logic on Words

J-E. Pin

IBP-Litp 1994/53: Rapport de Recherche Litp / Litp research reports
15 pages - Décembre/December 1994 - Document en anglais.

Titre / Title: Logic on Words

Résumé : Ce dialogue entre Quisani, l'étudiant imaginaire de Yuri Gurevich, et l'auteur, doit être publié dans la "Logic in Computer Science Column" du Bulletin de l'EATCS. Il s'adresse donc 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, is to be published in the "Logic in Computer Science Column" of the EATCS Bulletin. It is therefore 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 rôle of first order formulæ is emphasized. The quantifier hierarchies on these formulæ are an occasion to present open problems.

Publications internes Litp 1994 / Litp research reports 1994