$ La caractérisation (aa) ^ * $ dans la première logique de commande

Question

Dans ma description de classe de complexité, on nous a demandé de trouver une formule qui caractérise le $ (aa) langue ^ * $ (sur l'alphabet $ \ {a \} $) avec une première formule d'ordre sur la langue $ \ {<, P_A \} $.

Ce fut la première classe, donc je vais rappeler ce que nous avons appris à être sûr que je compris. Pour un $ L -formule $ $ \ phi $ nous associons une langue $ \ mathcal L (\ phi) $ qui est la classe de tous les $ L $ dans lequel -les structures $ \ phi $ est valide.

Dans mon cas, nous sommes alors à la recherche d'un $ \ {<, P_A \} $ - formule pour laquelle les mots de même longueur sont des modèles. Je suppose que je dois dire en $ \ phi $ que $ <$ est un ordre total, afin que je puisse interpréter les modèles comme des mots, et que $ \ forall x, P_A (x) $ à dire que tous les points sont étiquetés comme 'une'. Mais comment dire qu'il doit y avoir un nombre pair de points dans le modèle? La définition d'avoir un nombre pair de points semble récursive, donc j'ai l'impression qu'une formule pour $ (aa) ^ * $ devrait être d'une longueur infinie dans la logique du premier ordre ..

Answer 1

Réponse courte . Il n'y a pas de formule de premier ordre, vous avez besoin d'une deuxième formule d'ordre monadique.

Détails . Ceci peut être prouvé en utilisant directement un argument de jeux Ehrenfeucht-Fraïsse si vous voulez rester à l'intérieur logique, mais la vraie réponse à votre question est la conjonction de trois résultats.

[1] Büchi (1960):. Langue A est monadique du second ordre exprimable ssi il est régulier
[2] McNaughton-Pappert (1971): la langue A est premier ordre exprimable IFF est sans étoile
. Automata contre-libre. Monographie 65. Avec une annexe de William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9.
[3] Schützenberger (1965): Une langue régulière est sans étoile si et seulement si son syntaxique monoid est apériodique. Sur monoïdes finis ayant seulement des sous-groupes triviaux

[3] donne un algorithme pour décider si une langue régulière donnée est sans étoile (et, par conséquent, de premier ordre exprimable, par [2]). Maintenant, le monoïde syntaxique de $ (aa) ^ * $ est le groupe cyclique d'ordre 2 $, ce qui est apériodique. Pour obtenir une deuxième formule d'ordre monadique, vous devez d'abord avoir premier ordre « macros » pour exprimer $ \ min $, $ \ max $ et + 1 $ et la seconde formule de commande suivante fera le travail $$ \ Existe X \ \ forall x \ (\ min \ X \ wedge \ max \ notin X) \ coin (x \ in X \ leftrightarrow x + 1 \ notin X) $$