避けられないパターン

数学と理論計算機科学では、パターンが任意の有限アルファベット上で避けられない場合、 そのパターンは避けられないパターンと呼ばれます。

単語と同様に、パターン (用語とも呼ばれる) は、あるアルファベット上の記号のシーケンスです。

パターンの最小多重度はで、 はパターン におけるシンボルの出現回数です。言い換えれば、における最も出現頻度の低いシンボルのにおける出現回数です。 ${\displaystyle p}$${\displaystyle m(p)=\min(\mathrm {count_{p}} (x):x\in p)}$${\displaystyle \mathrm {count_{p}} (x)}$${\displaystyle x}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p}$

有限のアルファベットとが与えられたとき、 （ここで はのクリーネ星を表す）となるような非消去半群射が存在するとき、単語はパターンのインスタンスとなります。非消去とは、すべての に対して（ここで は空の文字列を表す）が成立することを意味します。 ${\displaystyle \Sigma }$${\displaystyle \Delta }$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle p\in \Delta ^{*}}$ ${\displaystyle f:\Delta ^{*}\rightarrow \Sigma ^{*}}$${\displaystyle f(p)=x}$${\displaystyle \Sigma ^{*}}$${\displaystyle \Sigma }$${\displaystyle f(a)\neq \varepsilon }$${\displaystyle a\in \Delta }$${\displaystyle \varepsilon }$

の要素 (サブワードまたはサブストリングとも呼ばれる) が のインスタンスである場合、その単語はパターンに一致する、またはに遭遇すると言われます。それ以外の場合、は を回避する、または フリーであると言われます。この定義は、「サブストリング」の一般化された定義に基づいて、 無限 の場合に一般化できます。${\displaystyle w}$${\displaystyle p}$${\displaystyle w}$${\displaystyle p}$${\displaystyle w}$${\displaystyle p}$${\displaystyle p}$${\displaystyle w}$

十分に長い各単語が に一致しなければならない場合、有限アルファベット上でパターンは避けられません。正式には、 の場合です。それ以外の場合、は上で回避可能であり、これはを回避する単語がアルファベット上に無限に存在することを意味します。 ${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle x\in \Sigma ^{*}}$${\displaystyle p}$${\displaystyle \exists n\in \mathrm {N} .\ \forall x\in \Sigma ^{*}.\ (|x|\geq n\implies x{\text{ matches }}p)}$${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle \Sigma }$${\displaystyle p}$

ケーニッヒの補題によれば、パターンは上で回避可能であるため、を回避する無限語が存在する必要がある。^[1]${\displaystyle p}$${\displaystyle \Sigma }$ ${\displaystyle w\in \Sigma ^{\omega }}$${\displaystyle p}$

パターンとアルファベットが与えられます。-free word は、かつ が である場合に、上の最大-free wordになります。 ${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle p}$${\displaystyle w\in \Sigma ^{*}}$${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle aw}$${\displaystyle wa}$${\displaystyle p}$ ${\displaystyle \forall a\in \Sigma }$

パターンは、任意の有限アルファベット上で が避けられない 場合、避けられないパターン (ブロッキング項とも呼ばれる)です。${\displaystyle p}$${\displaystyle p}$

パターンが避けられず、特定のアルファベットに限定されていない場合、デフォルトでは有限のアルファベットに対しては避けられません。逆に、パターンが避けられず、特定のアルファベットに限定されていない場合、デフォルトでは有限のアルファベットに対しては避けられます。

パターンが-回避可能とは、サイズ のアルファベット上で が回避可能である場合です。そうでない場合、は -回避不可能であり、サイズ のすべてのアルファベット上で が回避不可能であることを意味します。^[2]${\displaystyle p}$${\displaystyle k}$${\displaystyle p}$${\displaystyle \Sigma }$${\displaystyle k}$${\displaystyle p}$${\displaystyle k}$${\displaystyle p}$${\displaystyle k}$

パターンが-回避可能であれば、 はすべての に対して -回避可能です。 ${\displaystyle p}$${\displaystyle k}$${\displaystyle p}$${\displaystyle g}$${\displaystyle g\geq k}$

回避可能なパターンの有限集合が与えられたとき、のすべてのパターンを回避するような無限単語が存在する。^[1]でのすべてのパターンを回避するような最小アルファベットのサイズを表すとします。 ${\displaystyle S=\{p_{1},p_{2},...,p_{i}\}}$${\displaystyle w\in \Sigma ^{\omega }}$${\displaystyle w}$${\displaystyle S}$${\displaystyle \mu (S)}$${\displaystyle \Sigma '}$${\displaystyle \exists w'\in {\Sigma '}^{\omega }}$${\displaystyle S}$

パターンの回避可能性指数は、が回避可能であり、 が回避不可能であるような最小のものである。^[1]${\displaystyle p}$${\displaystyle k}$${\displaystyle p}$${\displaystyle k}$${\displaystyle \infty }$${\displaystyle p}$

• パターンが回避可能であるとは、回避可能なパターンのインスタンスである場合である。^[3]${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle p}$
• 回避可能なパターンをパターンの因子とすると、も回避可能となる。^[3]${\displaystyle p}$${\displaystyle q}$${\displaystyle q}$
• パターンが避けられないのは、 が何らかの避けられないパターンの要因である場合のみです。${\displaystyle q}$${\displaystyle q}$${\displaystyle p}$
• 避けられないパターンと に含まれない記号が与えられた場合、 は避けられません。^[3]${\displaystyle p}$${\displaystyle a}$${\displaystyle p}$${\displaystyle pap}$
• 避けられないパターンが与えられた場合、逆転は避けられません。${\displaystyle p}$ ${\displaystyle p^{R}}$
• 避けられないパターンが与えられた場合、が にちょうど1回出現するような記号が存在する。^[3]${\displaystyle p}$${\displaystyle a}$${\displaystyle a}$${\displaystyle p}$
• がパターンの異なるシンボルの数を表すとします。 の場合、 は回避可能です。^[3]${\displaystyle n\in \mathrm {N} }$${\displaystyle p}$${\displaystyle |p|\geq 2^{n}}$${\displaystyle p}$

アルファベット が与えられると、および に対してZimin単語 (パターン) が再帰的に定義されます。 ${\displaystyle \Delta =\{x_{1},x_{2},...\}}$${\displaystyle Z_{n+1}=Z_{n}x_{n+1}Z_{n}}$${\displaystyle n\in \mathrm {Z} ^{+}}$${\displaystyle Z_{1}=x_{1}}$

ジミン語はすべて避けられない。^[4]

単語が避けられないのは、それがZimin語の要素である場合のみです。^[4]${\displaystyle w}$

有限のアルファベット が与えられたとき、がすべての に対して一致する最小の を表すとします。次の性質があります: ^[5]${\displaystyle \Sigma }$${\displaystyle f(n,|\Sigma |)}$${\displaystyle m\in \mathrm {Z} ^{+}}$${\displaystyle w}$${\displaystyle Z_{n}}$${\displaystyle w\in \Sigma ^{m}}$

• ${\displaystyle f(1,q)=1}$
• ${\displaystyle f(2,q)=2q+1}$
• ${\displaystyle f(3,2)=29}$
• ${\displaystyle f(n,q)\leq {^{n-1}q}=\underbrace {q^{q^{\cdot ^{\cdot ^{q}}}}} _{n-1}}$

${\displaystyle Z_{n}}$は、年以来アルファベットによって構築された最長の避けられないパターンです。 ${\displaystyle \Delta =\{x_{1},x_{2},...,x_{n}\}}$${\displaystyle |Z_{n}|=2^{n}-1}$

あるアルファベット 上のパターンが与えられたとき、次が成り立つような のサブセットが存在する場合、 はに対して自由であると言います。${\displaystyle p}$${\displaystyle \Delta }$${\displaystyle x\in \Delta }$${\displaystyle p}$${\displaystyle A,B}$${\displaystyle \Delta }$

1. ${\displaystyle uv}$は の因数であり、↔ は の因数であり、${\displaystyle p}$${\displaystyle u\in A}$${\displaystyle uv}$${\displaystyle p}$${\displaystyle v\in B}$
2. ${\displaystyle x\in A\backslash B\cup B\backslash A}$

たとえば、 とすると、上記の条件を満たす が 存在するため、 はに対して自由です。${\displaystyle p=abcbab}$${\displaystyle b}$${\displaystyle p}$${\displaystyle A=ac,B=b}$

に対して が自由であり、からのすべての出現を除去することによって得られるようなシンボルが存在する場合、パターンはパターン に簡約されます。この関係を で表します。 ${\displaystyle p\in \Delta ^{*}}$ ${\displaystyle q}$${\displaystyle x\in \Delta }$${\displaystyle x}$${\displaystyle p}$${\displaystyle q}$${\displaystyle x}$${\displaystyle p}$${\displaystyle p{\stackrel {x}{\rightarrow }}q}$

たとえば、 とすると、 は に対して自由であるため、は に簡約できます。 ${\displaystyle p=abcbab}$${\displaystyle p}$${\displaystyle q=aca}$${\displaystyle b}$${\displaystyle p}$

単語に空き文字がない場合、その単語はロックされていると言われ、したがって短縮することはできません。^[6]${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$

パターンが与えられた場合、が に簡約されがに簡約される場合、 がに簡約されます。この関係を で表します。 ${\displaystyle p,q,r}$${\displaystyle p}$${\displaystyle q}$${\displaystyle q}$${\displaystyle r}$${\displaystyle p}$${\displaystyle r}$${\displaystyle p{\stackrel {*}{\rightarrow }}r}$

パターンが避けられないのは、長さ1の単語に簡約される場合のみである。したがって、およびとなる。^{[7] [4]}${\displaystyle p}$${\displaystyle p}$${\displaystyle \exists w}$${\displaystyle |w|=1}$${\displaystyle p{\stackrel {*}{\rightarrow }}w}$

単純なグラフ が与えられた場合、シーケンス がに一致するような単純なパスが存在する場合、エッジの色付けはパターンに一致します。それ以外の場合は、を回避するか、 が -フリーであると言われます。 ${\displaystyle G=(V,E)}$ ${\displaystyle c:E\rightarrow \Delta }$${\displaystyle p}$ ${\displaystyle P=[e_{1},e_{2},...,e_{r}]}$${\displaystyle G}$${\displaystyle c(P)=[c(e_{1}),c(e_{2}),...,c(e_{r})]}$${\displaystyle p}$${\displaystyle c}$${\displaystyle p}$${\displaystyle p}$

同様に、シーケンスがに一致するような単純なパスが存在する場合、頂点の色付けはパターンに一致します。 ${\displaystyle c:V\rightarrow \Delta }$${\displaystyle p}$ ${\displaystyle P=[c_{1},c_{2},...,c_{r}]}$${\displaystyle G}$${\displaystyle c(P)}$${\displaystyle p}$

パターン彩色数は、グラフ上の-free 頂点彩色に必要な最小の異なる色数です。 ${\displaystyle \pi _{p}(G)}$${\displaystyle p}$${\displaystyle c}$${\displaystyle G}$

が最大次数がを超えないすべての単純グラフの集合であると します。 ${\displaystyle \pi _{p}(n)=\max\{\pi _{p}(G):G\in G_{n}\}}$${\displaystyle G_{n}}$${\displaystyle n}$

同様に、エッジカラーリングに対して 、およびが定義されます。${\displaystyle \pi _{p}'(G)}$${\displaystyle \pi _{p}'(n)}$

が によって制限され、のみが に依存する場合、グラフ上でパターンを回避できます。 ${\displaystyle p}$${\displaystyle \pi _{p}(n)}$${\displaystyle c_{p}}$${\displaystyle c_{p}}$${\displaystyle p}$

• 単語の回避は、グラフの回避の特殊なケースとして表現できます。したがって、パターンが任意の有限アルファベット上で回避可能であるのは、すべての に対してである場合のみです。ここで、は頂点が連結されたグラフです。${\displaystyle p}$${\displaystyle \pi _{p}(P_{n})\leq c_{p}}$${\displaystyle n\in \mathrm {Z} ^{+}}$${\displaystyle P_{n}}$${\displaystyle n}$

絶対定数が存在し、となるすべてのパターンに対してとなる。^[8]${\displaystyle c}$${\displaystyle \pi _{p}(n)\leq cn^{\frac {m(p)}{m(p)-1}}\leq cn^{2}}$${\displaystyle p}$${\displaystyle m(p)\geq 2}$

パターン が与えられた場合、は の異なるシンボルの数を表します。 の場合、 はグラフ上で回避可能です。 ${\displaystyle p}$${\displaystyle n}$${\displaystyle p}$${\displaystyle |p|\geq 2^{n}}$${\displaystyle p}$

がすべての に対して偶数となるようなパターンが与えられた場合、すべての に対してとなり、頂点の完全グラフとなる。^[8]${\displaystyle p}$${\displaystyle count_{p}(x)}$${\displaystyle x\in p}$${\displaystyle \pi _{p}'(K_{2}^{k})\leq 2^{k}-1}$${\displaystyle k\geq 1}$${\displaystyle K_{n}}$${\displaystyle n}$

となるパターンと任意の木が与えられたとき、を のすべての回避可能なサブパターンとその反射の集合とします。すると となります。^[8]${\displaystyle p}$${\displaystyle m(p)\geq 2}$ ${\displaystyle T}$${\displaystyle S}$${\displaystyle p}$${\displaystyle \pi _{p}(T)\leq 3\mu (S)}$

となるパターンと次数 の木が与えられたとする。をのすべての回避可能なサブパターンとその反射の集合とすると、 となる。^[8]${\displaystyle p}$${\displaystyle m(p)\geq 2}$ ${\displaystyle T}$${\displaystyle n\geq 2}$${\displaystyle S}$${\displaystyle p}$${\displaystyle \pi _{p}'(T)\leq 2(n-1)\mu (S)}$

• Thue-Morse数列は立方体がなく、重なりもないので、パターンやを回避できます。^[2]${\displaystyle xxx}$${\displaystyle xyxyx}$
• 平方自由単語とはパターンを避ける単語である。Thue-Morse数列の最初の差をとることで得られるアルファベット上の単語は、無限平方自由単語の例である。^{[9] [10]}${\displaystyle xx}$${\displaystyle \{0,\pm 1\}}$
• とのパターンは、Zimin語の要素であるため、どのアルファベットでも避けられません。^{[11] [1]}${\displaystyle x}$${\displaystyle xyx}$
• のパワーパターンは2回避可能である。^[1]${\displaystyle x^{n}}$${\displaystyle n\geq 3}$
• すべてのバイナリパターンは3つのカテゴリに分類できます。^[1]
  • ${\displaystyle \varepsilon ,x,xyx}$避けられない。
  • ${\displaystyle xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy}$回避可能性指数は3です。
  • その他は回避可能性指数が 2 です。
• ${\displaystyle abwbaxbcyaczca}$他の禁止語と同様に回避可能性指数は4である。^[6]
• ${\displaystyle abvacwbaxbcycdazdcd}$回避可能性指数は5である^。[12]
• 反復しきい値は、サイズ のアルファベットで が回避可能な指数の下限です。デジャンの定理も参照してください。${\displaystyle RT(n)}$${\displaystyle k}$${\displaystyle x^{k}}$${\displaystyle n}$

• 回避可能性指数が 6 になるような回避可能なパターンはありますか?${\displaystyle p}$${\displaystyle p}$
• 任意のパターンが与えられた場合、回避可能性指数を決定するアルゴリズムはあるか？^[1]${\displaystyle p}$${\displaystyle p}$

• アルーシュ、ジャン=ポール、シャリット、ジェフリー(2003)。自動シーケンス: 理論、アプリケーション、一般化。ケンブリッジ大学出版局。ISBN 978-0-521-82332-6.ZBL1086.11015  。​
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009)。単語の組合せ論。クリストッフェル単語と単語内の繰り返し。CRMモノグラフシリーズ。第27巻。プロビデンス、ロードアイランド州：アメリカ数学会。ISBN 978-0-8218-4480-9.ZBL1161.68043  。​
• ロテール、M. (2011)。単語の代数的組合せ論。数学とその応用百科事典。第90巻。ジャン・ベルステルとドミニク・ペランによる序文付き（2002年ハードカバー版の再版）。ケンブリッジ大学出版局。ISBN 978-0-521-18071-9.ZBL1221.68183  。​
• ピテアス・フォッグ、N. (2002)。Berthé, ヴァレリー;フェレンチ、セバスチャン。モーデュイ、クリスチャン。シーゲル、A. (編)。力学、算術、組み合わせ論における置換。数学の講義ノート。 Vol. 1794年。ベルリン：シュプリンガー・フェルラーク。ISBN 3-540-44141-7.ZBL1014.11015  .​