Logic on words
Jean-Éric Pin · 2001
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 Buchi's sequential calculus and the theory of finite automata. In particular, the essential role of first order formulae is emphasized. The quantifier hierarchies on these formulae are an occasion to present open problems.