Monoide Faktorisierung - Monoid factorisation

In der Mathematik ist eine Faktorisierung eines freien Monoids eine Folge von Teilmengen von Wörtern mit der Eigenschaft, dass jedes Wort im freien Monoid als eine Verkettung von Elementen aus den Teilmengen geschrieben werden kann. Der Chen- Fox - Lyndon Theorem besagt , dass die Lyndon Worte eine Faktorisierung liefern. Der Satz von Schützenberger bezieht die Definition einer multiplikativen Eigenschaft mit einer additiven Eigenschaft.

Sei A * das freie Monoid auf einem Alphabet A . Sei X i eine Folge von Teilmengen von A *, die durch eine total geordnete Indexmenge I indiziert sind . Eine Faktorisierung eines Wortes w in A * ist ein Ausdruck

mit und . Einige Autoren kehren die Reihenfolge der Ungleichungen um.

Chen-Fox-Lyndon-Theorem

Ein Lyndon-Wort über einem vollständig geordneten Alphabet A ist ein Wort, das lexikographisch weniger ist als alle seine Drehungen. Das Chen-Fox-Lyndon-Theorem besagt, dass jede Zeichenkette auf einzigartige Weise gebildet werden kann, indem eine nicht ansteigende Folge von Lyndon-Wörtern verkettet wird. Nehmen wir also X l als die Singleton-Menge { l  } für jedes Lyndon-Wort l und die Indexmenge L der Lyndon-Wörter lexikographisch geordnet, erhalten wir eine Faktorisierung von A * . Eine solche Faktorisierung findet sich in linearer Zeit .

Hallenworte

Der Hall-Satz bietet eine Faktorisierung. Tatsächlich sind Lyndon-Wörter ein Sonderfall von Hall-Wörtern. Der Artikel über Hall-Wörter skizziert alle Mechanismen, die zum Nachweis dieser Faktorisierung erforderlich sind.

Halbierung

Eine Halbierung eines freien Monoids ist eine Faktorisierung mit nur zwei Klassen X 0 , X 1 .

Beispiele:

A = { a , b }, X 0 = { a * b }, X 1 = { a }.

Wenn X , Y sind disjunkte Mengen von nicht-leeren Worten, dann ist ( X , Y ) ist eine Halbierungs von A * , wenn und nur dann , wenn

Folglich gibt es für jede Partition P , Q von A + eine eindeutige Halbierung ( X , Y ) mit X einer Teilmenge von P und Y einer Teilmenge von Q .

Satz von Schützenberger

Dieser Satz besagt, dass eine Folge X i von Teilmengen von A * genau dann eine Faktorisierung bildet, wenn zwei der folgenden drei Aussagen gelten:

  • Jedes Element von A * hat mindestens einen Ausdruck in der erforderlichen Form;
  • Jedes Element von A * hat höchstens einen Ausdruck in der geforderten Form;
  • Jede konjugierte Klasse C trifft nur eines der Monoide M i = X i * und die Elemente von C in M i sind in M i konjugiert .

Siehe auch

Verweise