Loading article…
数学とコンピュータ サイエンスにおいて、モーフィック ワードまたは代替ワードは、自由モノイドの特定のクラスの自己準同型から構成される記号の無限シーケンスです。
すべての自動シーケンスはモーフィックです。[1]
意味
f をアルファベットA上の自由モノイドA ∗の自己準同型とし、文字aが存在してf ( a ) =となる性質を持つものとする。空でない文字列sについて、 fはaで延長可能であるという。単語
は純粋形態語または純粋代替語である。これはa、f ( a ) 、f ( f ( a ) ) 、f ( f ( f ( a ) ) )、... というシーケンスの極限であることに注意する。これは明らかに自己準同型fの不動点である。自己準同型 f は文字aで始まる唯一のシーケンスである。[2] [3]一般に、形態語は純粋形態語のコーディングによる像、つまり文字を文字にマッピングする射である。[1]
モルフィックワードがA ∗上の延長可能なk一様射の不動点として構成される場合、そのワードはk自動的である。このようなシーケンスのn番目の項は、 kを基数とするnの数字を読み取る有限状態オートマトンによって生成できる。[1]
例
- トゥエ・モース数列は{0,1}上で2次元一様自己準同型0 → 01, 1 → 10によって生成される。[4] [5]
- フィボナッチ数列 は{ a , b }上で自己準同型a → ab , b → aによって生成される。[1] [4]
- トリボナッチ語は{ a , b , c }上で自己準同型a → ab , b → ac , c → aによって生成される。[5]
- ルディン・シャピロ数列は、2一様射a → ab、b → ac、c → db、d → dcの不動点にa、b → 0、c、d → 1の 符号化が続くことで得られる。[5]
- 通常の折り紙のシーケンスは、2一様射の不動点a → ab、b → cb、c → ad、d → cd に続いてコーディングa、b → 0、c、d → 1から得られる。 [6]
D0Lシステム
D0L システム(決定論的文脈自由リンデンマイヤー システム) は、アルファベットA上の自由モノイドA ∗の単語wとwで延長可能な射 σ によって表される。このシステムは無限 D0L 単語 ω = lim n →∞ σ n ( w ) を生成する。純粋にモルフィックな単語は D0L 単語であるが、その逆は成り立たない。しかし、 ω = u νが長さ | u | ≥ | w | の初期セグメントuを持つ無限 D0L 単語である場合、z ν は純粋にモルフィックな単語であり、zはAに含まれない文字である。[7]
参照
参考文献
- ^ abcd ロテール (2005) p.524
- ^ ロテール（2011）p.10
- ^ ホンカラ（2010）p.505
- ^ ロテール（2011）p.11
- ^ abc ロテール (2005) p.525
- ^ ロテール（2005）p.526
- ^ ホンカラ（2010）p.506
- アルーシュ、ジャン=ポール、シャリット、ジェフリー(2003)。自動シーケンス: 理論、アプリケーション、一般化。ケンブリッジ大学出版局。ISBN 978-0-521-82332-6.ZBL1086.11015 。
- Honkala, Juha (2010)。「純粋に代用的な単語の等式問題」。Berthé , Valérie、Rigo, Michel (編)。組合せ論、オートマトン、数論。数学とその応用百科事典。第 135 巻。ケンブリッジ:ケンブリッジ大学出版局。505 ～ 529 ページ。ISBN 978-0-521-51597-9.ZBL1216.68209 。
- ロテール、M. (2005)。単語に組み合わせ論を応用。数学とその応用の百科事典。 Vol. 105.ジャン・ベルステル、ドミニク・ペラン、マキシム・クロシュモア、エリック・ラポルト、メリヤル・モーリ、ナディア・ピサンティ、マリー＝フランス・サゴ、ゲシーヌ・ライナート、ソフィー・シュバス、マイケル・ウォーターマン、フィリップ・ジャケ、ヴォイチェフ・シュパンコウスキー、ドミニク・ポラロン、ジル・シェーファーによる共同作品。ローマ人コルパコフ、グレゴリー・クチェロフ、ジャン＝ポール・アルーシュ、ヴァレリー・ベルテ。ケンブリッジ：ケンブリッジ大学出版局。ISBN 0-521-84802-4.ZBL1133.68067 。
- ロテール、M. (2011)。単語の代数的組合せ論。数学とその応用百科事典。第90巻。ジャン・ベルステルとドミニク・ペランによる序文付き（2002年ハードカバー版の再版）。ケンブリッジ大学出版局。ISBN 978-0-521-18071-9.ZBL1221.68183 。
さらに読む
- Cassaigne, Julien; Karhumäki, Juhani (1997). 「Toeplitz 語、一般化された周期性、および周期的に反復される射影」. European Journal of Combinatorics . 18 (5): 497–510. doi : 10.1006/eujc.1996.0110 . Zbl 0881.68065.