トレースモノイド

Generalization of strings in computer science

コンピュータサイエンスにおいて、トレースとは文字列の同値類であり、文字列中の特定の文字は交換可能で、他の文字は交換不可能である。トレースは、すべての文字が特定の順序を持​​つという要件を緩和し、代わりに特定の並べ替えが起こり得る不確定な順序付けを許容することで、文字列の概念を一般化する。逆に、トレースは、すべての順序付けにおいて完全な同値性を要求するのではなく、文字の不完全な順序付けを指定できるようにすることで、重複度を持つ集合の概念を一般化する。トレースモノイドまたは自由部分可換モノイドは、トレースのモノイドである。

トレースは、1969年にピエール・カルティエとドミニク・フォアタによってマクマホンのマスター定理の組合せ論的証明のために導入されました。トレースは並行計算理論で用いられ、可換文字は互いに独立して実行できるジョブの部分を表し、非可換文字はロック、同期ポイント、またはスレッドの結合を表します。^[1]

トレースモノイドは、自由モノイド（有限長の文字列全体の集合）から次のように構築されます。まず、可換な文字の集合が独立関係によって与えられます。これにより、同値な文字列の同値関係が誘導されます。同値類の要素がトレースです。次に、同値関係によって自由モノイドの要素が同値類の集合に分割されます。結果もモノイドであり、これは商モノイドであり、トレースモノイドと呼ばれます。トレースモノイドは普遍的であり、すべての依存準同型（以下を参照）モノイドは実際には同型です。

トレースモノイドは、並行計算をモデル化するために広く用いられ、プロセス計算の基礎を形成します。トレース理論の研究対象でもあります。トレースモノイドの有用性は、依存グラフのモノイドと同型であることに由来します。そのため、代数的手法をグラフに適用することができ、またその逆も可能です。また、トレースモノイドは、1台以上のコンピュータ上でスケジュールされているすべてのプロセスのコンテキストにおいて、個々のプロセスの計算履歴をモデル化する履歴モノイドとも同型です。

トレース

生成元集合 上の自由モノイド、つまりアルファベット で書かれたすべての文字列の集合をで表すものとします。アスタリスクはクリーネスターの標準表記です。アルファベット上の独立関係は、文字列の集合上に対称二項関係を誘導します。つまり、2つの文字列が関連して いる場合、かつ とおよびとなるペアが存在する場合に限ります。ここで、とは文字列（ の要素）であり、とは文字（ の要素）であると理解されます。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle I}$ ${\displaystyle \Sigma }$ ${\displaystyle \sim }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle u,v}$ ${\displaystyle u\sim v,}$ ${\displaystyle x,y\in \Sigma ^{*}}$ ${\displaystyle (a,b)\in I}$ ${\displaystyle u=xaby}$ ${\displaystyle v=xbay}$ ${\displaystyle u,v,x}$ ${\displaystyle y}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \Sigma }$

トレースはの反射的推移閉包として定義されます。したがって、トレースは上の同値関係であり、 で表されます。ここで、はおよびに対応する依存関係です。異なる独立性または依存関係は、異なる同値関係をもたらします。 ${\displaystyle \sim }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \equiv _{D}}$ ${\displaystyle D}$ ${\displaystyle I.}$ ${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$ ${\displaystyle I=(\Sigma \times \Sigma )\setminus D.}$

推移閉包は、すべての に対してとなるような文字列の列が存在するとき、かつそのときに限り となることを意味する。トレースは 上のモノイド演算、すなわち連結の下で安定であり、したがって上の合同関係である。 ${\displaystyle u\equiv _{D}v}$ ${\displaystyle (w_{0},w_{1},\cdots ,w_{n})}$ ${\displaystyle u\sim w_{0},}$ ${\displaystyle v\sim w_{n},}$ ${\displaystyle w_{i}\sim w_{i+1}}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \equiv _{D}}$ ${\displaystyle \Sigma ^{*}.}$

トレースモノイドは、一般的には と表記され、商モノイドとして定義される。 ${\displaystyle \mathbb {M} (D)}$

${\displaystyle \mathbb {M} (D)=\Sigma ^{*}/\equiv _{D}.}$

準同型性

${\displaystyle \phi _{D}:\Sigma ^{*}\to \mathbb {M} (D)}$

は一般に自然準​​同型または標準準同型と呼ばれます。自然または標準という用語がふさわしいのは、この射が普遍的な性質を体現しているという事実から来ており、これについては後のセクションで説明します。

トレースモノイドは と表記されます。は独立関係です。独立関係の代わりに交換関係を用いることもできます。これは、文字がそれらの文字からなる文字列の自由モノイドにおいて「自身と交換可能」であるため、 のすべての対角要素も含む点で独立関係とは異なります。 ${\displaystyle M(\Sigma ,I)}$ ${\displaystyle I}$ ${\textstyle \Sigma \times \Sigma }$

例

アルファベットを考えてみましょう。依存関係として考えられるのは ${\displaystyle \Sigma =\{a,b,c\}}$

${\displaystyle {\begin{matrix}D&=&\{a,b\}\times \{a,b\}\quad \cup \quad \{a,c\}\times \{a,c\}\\&=&\{a,b\}^{2}\cup \{a,c\}^{2}\\&=&\{(a,b),(b,a),(a,c),(c,a),(a,a),(b,b),(c,c)\}.\end{matrix}}}$

対応する独立性は

${\displaystyle I_{D}=\{(b,c)\,,\,(c,b)\}.}$

したがって、文字は可換である。したがって、例えば、文字列のトレース同値類は次のようになる。 ${\displaystyle b,c}$ ${\displaystyle abababbca}$

${\displaystyle [abababbca]_{D}=\{abababbca\,,\;abababcba\,,\;ababacbba\}}$

そして同値類はトレースモノイドの要素になります。 ${\displaystyle [abababbca]_{D}}$

プロパティ

打ち消し特性は、右打ち消しにおいて等価性が維持されることを示します。つまり、ならばとなります。ここで、 という表記は右打ち消し、つまり文字列wの右側から最初に出現する文字aを削除することを表します。等価性は左打ち消しによっても維持されます。いくつかの系が続きます。 ${\displaystyle w\equiv v}$ ${\displaystyle (w\div a)\equiv (v\div a)}$ ${\displaystyle w\div a}$

• 埋め込み:文字列xとyに対して が成り立つ場合のみ。したがって、トレースモノイドは構文的モノイドである。^{[不合理。トーク:トレースモノイド#構文的モノイドとして を参照]} ${\displaystyle w\equiv v}$ ${\displaystyle xwy\equiv xvy}$
• 独立性： かつ ならば、aはbと独立である。つまり、 である。さらに、かつとなるような文字列w が存在する。 ${\displaystyle ua\equiv vb}$ ${\displaystyle a\neq b}$ ${\displaystyle (a,b)\in I_{D}}$ ${\displaystyle u\equiv wb}$ ${\displaystyle v\equiv wa}$
• 射影規則:文字列射影では同値性が維持されるため、 であればとなります。 ${\displaystyle w\equiv v}$ ${\displaystyle \pi _{\Sigma }(w)\equiv \pi _{\Sigma }(v)}$

リーバイの補題の強い形は痕跡に対して成り立つ。具体的には、文字列u , v , x , yに対して、文字列および が存在し、任意の文字および に対してが に出現し、が に出現し、 ${\displaystyle uv\equiv xy}$ ${\displaystyle z_{1},z_{2},z_{3}}$ ${\displaystyle z_{4}}$ ${\displaystyle (w_{2},w_{3})\in I_{D}}$ ${\displaystyle w_{2}\in \Sigma }$ ${\displaystyle w_{3}\in \Sigma }$ ${\displaystyle w_{2}}$ ${\displaystyle z_{2}}$ ${\displaystyle w_{3}}$ ${\displaystyle z_{3}}$

${\displaystyle u\equiv z_{1}z_{2},\qquad v\equiv z_{3}z_{4},}$

${\displaystyle x\equiv z_{1}z_{3},\qquad y\equiv z_{2}z_{4}.}$^[2]

普遍的な財産

依存射（依存Dに関して）は、

${\displaystyle \psi :\Sigma ^{*}\to M}$

モノイドMに、次のような「通常の」トレース特性が成り立つ。

1.は、 ${\displaystyle \psi (w)=\psi (\varepsilon )}$ ${\displaystyle w=\varepsilon }$

2.は、 ${\displaystyle (a,b)\in I_{D}}$ ${\displaystyle \psi (ab)=\psi (ba)}$

3.は、 ${\displaystyle \psi (ua)=\psi (v)}$ ${\displaystyle \psi (u)=\psi (v\div a)}$

4.そして、 ${\displaystyle \psi (ua)=\psi (vb)}$ ${\displaystyle a\neq b}$ ${\displaystyle (a,b)\in I_{D}}$

依存射は普遍的である。これは、与えられた固定された依存Dに対して、 がモノイドMへの依存射であるならば、Mはトレースモノイド と同型であるという意味で普遍的である。特に、自然準同型は依存射である。 ${\displaystyle \psi :\Sigma ^{*}\to M}$ ${\displaystyle \mathbb {M} (D)}$

正規形

トレースモノイドの語には、2つのよく知られた正規形があります。1つはAnatolij V. AnisimovとDonald Knuthによる辞書式正規形であり、もう1つは1960年代にトレースモノイドの組み合わせ論を研究したPierre CartierとDominique FoataによるFoata正規形です。 ^[3]

Unicode の正規化形式標準分解(NFD) は、辞書式正規形式の例です。順序付けは、非ゼロの標準結合クラスを持つ連続する文字をそのクラスで並べ替えます。

トレース言語

形式言語が、すべての可能な文字列の集合のサブセットと見なすことができるのと同様に、トレース言語は、すべての可能なトレースのサブセットとして定義されます。 ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \mathbb {M} (D)}$

あるいは、同じことであるが、ある言語がトレース言語である、あるいは依存性Dと一貫性があると言われるのは、 ${\displaystyle L\subseteq \Sigma ^{*}}$

${\displaystyle L=[L]_{D}}$

どこ

${\displaystyle [L]_{D}=\bigcup _{w\in L}[w]_{D}}$

文字列の集合のトレース閉包です。

参照

• トレースキャッシュ

注記

1. サンダー＆クリスティシ (2004) p.161
2. 命題2.2、DiekertとMétivier 1997。
3. セクション2.3、DiekertとMétivier 1997。

参考文献

一般的な参考文献

• ディーケルト、フォルカー。イヴ・メティヴィエ（1997）、「部分的転流と痕跡」、Rozenberg、G. Salomaa, A. (編)、形式言語ハンドブック Vol. 3; 『Beyond Words』 、シュプリンガー・フェルラーク、ベルリン、 457 ～ 534ページ 、ISBN 3-540-60649-1
• ロテール, M. (2011),語の代数的組合せ論, 数学とその応用百科事典, 第90巻, ジャン・ベルステルとドミニク・ペランによる序文付き（2002年ハードカバー版の再版）, ケンブリッジ大学出版局, ISBN 978-0-521-18071-9、Zbl  1221.68183
• アントニ・マズルキエヴィチ、「トレース理論入門」、pp 3–41、V. ディーケルト、G. ローゼンバーグ編『トレースの書』 、(1995) ワールド・サイエンティフィック、シンガポールISBN 981-02-2058-8
• Volker Diekert, Combinatorics on traces , LNCS 454, Springer, 1990, ISBN 3-540-53031-2、9～29ページ
• サンダー、ジョゼフ。 Crstici、Borislav (2004)、Handbook of Number Theory II、Dordrecht: Kluwer Academic、pp.  32–36、ISBN 1-4020-2546-7、Zbl  1079.11001

重要な出版物

• ピエール・カルティエとドミニク・フォアタ、交換と配置の問題の組み合わせ、数学の講義ノート 85、シュプリンガー・フェルラーク、ベルリン、1969 年、新しい付録付きの 2006 年の無料再版
• アントニ・マズルキエヴィチ、「並行プログラムスキームとその解釈」、DAIMIレポートPB78、オーフス大学、1977年

Retrieved from "https://en.wikipedia.org/w/index.php?title=Trace_monoid&oldid=1293031091"