$（aa）^*$を一次ロジックの特徴

Question

私の説明的な複雑さのクラスでは、言語$（aa）^*$（alphabet $ {a } $を超えて）を特徴付ける式を見つけるように求められました$ {<<<< 、p_a } $。

これが最初のクラスだったので、私が理解したことを確実にしたことを学んだことを思い出します。 $ l $ -Formula $ phi $に、言語$ mathcal l（ phi）$を関連付けます。

私の場合、$ {<、p_a } $を探しています - 偶数の長さの単語がモデルである式です。 $ phi $で$ <$は合計順序であると言わなければならないので、モデルを単語として解釈できます。 「A」。しかし、モデルに偶数のポイントが必要だと言う方法は？偶数のポイントを持つことの定義は再帰的であるように思われるので、$（aa）^*$の式は1次ロジックで無限の長さであるべきであるという印象を受けます。

Answer 1

短い答え. 。そのような1次式はありません。モナディックの二次式が必要です。

詳細. 。これは、ロジックの中にとどまりたい場合は、ehrenfeucht-fraïsséゲームの引数を使用して直接証明できますが、質問に対する本当の答えは、3つの結果の結合です。

1]Büchi（1960）：言語は、通常の場合はモナディックの二次表現可能です。
2] McNaughton-Pappert（1971）：言語は、スターフリーである場合、一次表現可能な場合です。
カウンターフリーオートマトン。研究モノグラフ65.ウィリアム・ヘネマンによる付録付き。 MITプレス。 p。 48. ISBN 0-262-13076-9。
3]Schützenberger（1965）：通常の言語は、その場合にのみスターフリーです 構文モノイド 非周期的です。 些細なサブグループのみを備えた有限モノイドについて

3]は、特定の正規言語が星なしであるかどうかを決定するアルゴリズムを提供します（したがって、[2]によって1次表現可能なもの）。これで、$（aa）^*$の構文モノイドは、$ 2 $の周期的なグループです。これは無周期ではありません。 Monadic Second Orderフォーミュラを取得するには、最初に$ min $、$ max $、$+1 $を表現するための1次「Macros」が必要です。 forall x （ min in x wedge max notin x） wedge（x in x leftrightarrow x+1 notin x）$$