From ultrafilters on words to
the expressive power of a fragment of logic
M. Gehrke, A. Krebs and J.-É. Pin
Résumé : Nous donnons une méthode pour
spécifier des équations en ultrafiltres et identifier leurs
projections sur l'ensemble des mots profinis. Soit B l'ensemble
des langages décrits par des énoncés du premier
ordre utilisant des prédicats unaires pour chaque lettre, des
prédicats numériques uniformes unaires arbitraires et un
prédicat pour la longueur d'un mot. Nous illustrons notre
méthode en donnant des équations profinies
caractérisant B ∩ Reg à partir
d'équations en ultrafiltres satisfaites par B. Cela suffit
à établir la décidabilité de l'appartenance
à B ∩ Reg
Abstract : We give a method for specifying ultrafilter equations
and identify their projections on the set of profinite words. Let
B be the set of languages captured by first-order sentences using
unary predicates for each letter, arbitrary uniform unary numerical
predicates and a predicate for the length of a word. We illustrate our
methods by giving profinite equations characterizing B ∩
Reg via ultrafilter equations satisfied by B. This suffices
to establish the decidability of the membership problem for B
∩
Reg.