Der Fall uw  =  x und v =  wy des Lemmas von Levi

In der theoretischen Informatik und Mathematik , insbesondere im Bereich der Kombinatorik von Wörtern , besagt das Lemma von Levi , dass für alle Zeichenketten u , v , x und y gilt : Wenn uv  =  xy , dann existiert eine Zeichenkette w, sodass entweder

uw = x und v  =  wy (falls | u | ≤ | x |)

oder

u  =  xw und wv  =  y (falls | u | ≥ | x |)

Das heißt, es gibt eine Zeichenkette w, die „in der Mitte“ liegt und entweder der einen oder der anderen Seite zugeordnet werden kann. Das Lemma von Levi ist nach Friedrich Wilhelm Levi benannt , der es 1944 veröffentlichte. [ 1 ]

Anwendungen

Das Lemma von Levi kann wiederholt angewendet werden, um Wortgleichungen zu lösen ; in diesem Kontext wird es in Analogie zur Nielsen-Transformation für Gruppen manchmal auch als Nielsen-Transformation bezeichnet . Ausgehend von einer Gleichung x<sup>α </sup> = y<sup>β</sup> , wobei x und y die Unbekannten sind, kann man sie (unter der Annahme |x| ≥ |y| , sodass ein t existiert, sodass x = y<sup> t</sup> ) in y<sup>tα</sup> = y<sup> β</sup> und somit in t<sup>α</sup> = β transformieren. Dieser Ansatz führt zu einem Substitutionsgraphen, der durch wiederholte Anwendung des Lemmas von Levi erzeugt wird. Wenn jede Unbekannte höchstens zweimal vorkommt, so nennt man eine Wortgleichung quadratisch; bei einer quadratischen Wortgleichung ist der durch wiederholte Anwendung des Lemmas von Levi erhaltene Graph endlich, sodass sich entscheiden lässt, ob eine quadratische Wortgleichung eine Lösung besitzt . [ 2 ] Ein allgemeineres Verfahren zur Lösung von Wortgleichungen ist der Algorithmus von Makanin . [ 3 ] [ 4 ]

Verallgemeinerungen

Das Obige ist als Levi-Lemma für Zeichenketten bekannt ; das Lemma kann in allgemeinerer Form in der Graphentheorie und der Monoidtheorie auftreten ; beispielsweise gibt es ein allgemeineres Levi-Lemma für Spuren , das ursprünglich von Christine Duboc stammt. [ 5 ] Mehrere Beweise des Levi-Lemmas für Spuren finden sich in „The Book of Traces“ . [ 6 ]

Ein Monoid, für das das Lemma von Levi gilt, besitzt die Äquiteilbarkeitseigenschaft . [ 7 ] Das freie Monoid der Zeichenketten und ihrer Verkettung besitzt diese Eigenschaft (nach dem Lemma von Levi für Zeichenketten), aber Äquiteilbarkeit allein reicht nicht aus, um die Freiheit eines Monoids zu garantieren. Ein äquiteilbares Monoid M ist jedoch genau dann frei, wenn zusätzlich ein Homomorphismus f von M in das Monoid der natürlichen Zahlen (freies Monoid mit einem Erzeuger) existiert, dessen Urbild von 0 genau das neutrale Element von M enthält . (Beachte, dass die Tatsache, dass f ein Homomorphismus ist, diese Eigenschaft nicht garantiert, da mehrere Elemente von M auf 0 abgebildet werden könnten.) [ 8 ] Ein Monoid, für das ein solcher Homomorphismus existiert, wird auch graduiert genannt (und der Homomorphismus f wird als Graduierung bezeichnet). [ 9 ]

Siehe auch

Anmerkungen

  1. ^ Levi, FW (1944), „Über Halbgruppen“, Bulletin of the Calcutta Mathematical Society , 36 : 141–146 , MR 0011694 , Zbl 0061.02405  Die
  2. ^ Matiyasevich, Yu. V. (1968), „Ein Zusammenhang zwischen Systemen von Wort- und Längengleichungen und Hilberts zehntem Problem“, Zap. Naučn. Sem. Leningrad. Otdel. Matte. Inst. Steklow. ( LOMI) , 8 : 132–144Die
  3. ^ Makanin, GS (1977), „Das Problem der Lösbarkeit von Gleichungen in einer freien Halbgruppe“, Mat. Sbornik , 103 (2), englische Übersetzung in Math. USSR Sbornik 32 (1977): 147–236 , Bibcode : 1977SbMat..32..129M , doi : 10.1070/SM1977v032n02ABEH002376
  4. ^ M. Lothaire (2002). „12“ . Algebraische Kombinatorik auf Wörtern . Cambridge University Press. ISBN 0-521-81220-8Die
  5. ^ Duboc, Chr. (1986), „Über einige Gleichungen in freien partiell kommutativen Monoiden“, Theoretical Computer Science , 46 : 159–174 , doi : 10.1016/0304-3975(86)90028-9
  6. ^ Volker Diekert; Grzegorz Rozenberg (Hrsg.) (1995). Das Buch der Spuren . World Scientific. S.  1–576 . ISBN 981-02-2058-8Die
  7. ^ Aldo de Luca; Stefano Varricchio (1999). Endlichkeit und Regularität in Halbgruppen und formalen Sprachen . Springer Berlin Heidelberg. S. 2. ISBN 978-3-642-64150-3Die
  8. ^ M. Lothaire (1997). Kombinatorik von Wörtern . Cambridge University Press. S. 13. ISBN 978-0-521-59924-5Die
  9. ^ Sakarovitch, Jacques (2009), Elemente der Automatentheorie , aus dem Französischen übersetzt von Reuben Thomas, Cambridge: Cambridge University Press , S. 26, ISBN 978-0-521-84425-3