Levi Lemma

A lemma Levi egy eredmény az elméleti számítógép-tudomány és a kombinatorika a szavak .

Államok

Az állítás a következő:

Levi lemma  -  Let , , , a szavak . Ha , akkor létezik olyan szó , hogy a következő két eset egyikében vagyunk: x{\ displaystyle x}y{\ displaystyle y}x′{\ displaystyle x '}y′{\ displaystyle y '}xy=x′y′{\ displaystyle xy = x'y '}z{\ displaystyle z}

• vagy , (ha );x=x′z{\ displaystyle x = x'z}y′=zy{\ displaystyle y '= zy}|x|≥|x′|{\ displaystyle | x | \ geq | x '|}
• vagy , (ha ).x′=xz{\ displaystyle x '= xz}y=zy′{\ displaystyle y = zy '}|x|≤|x′|{\ displaystyle | x | \ leq | x '|}

Példa

Vannak anti , alkotmányosan , alkotmányellenes , csak szavak.
Tehát anti . alkotmányosan = alkotmányellenes . elem , és még több | anti | | alkotmányellenes | akkor van az alkotmányos szó , például alkotmányellenes = anti . alkotmányosan és alkotmányosan = alkotmányos . lly≤{\ displaystyle \ leq}

Demonstráció

Pózoljunk

w=xy=x′y′=nál nél1nál nél2⋯nál nélnem{\ displaystyle w = xy = x'y '= a_ {1} a_ {2} \ cdots a_ {n}},

ahol a betűk vannak. Legyen az egész szám olyan nál nélk{\ displaystyle a_ {k}}én{\ displaystyle i}

x=nál nél1nál nél2⋯nál nélén,y=nál nélén+1⋯nál nélnem{\ displaystyle x = a_ {1} a_ {2} \ cdots a_ {i}, y = a_ {i + 1} \ cdots a_ {n}},

és ugyanúgy legyen az egész szám, hogy j{\ displaystyle j}

x′=nál nél1nál nél2⋯nál nélj,y′=nál nélj+1⋯nál nélnem{\ displaystyle x '= a_ {1} a_ {2} \ cdots a_ {j}, y' = a_ {j + 1} \ cdots a_ {n}}.

Ha , akkor és megvan , a |x|≤|x′|{\ displaystyle | x | \ leq | x '|}én≤j{\ displaystyle i \ leq j}x′=xz{\ displaystyle x '= xz}y=zy′{\ displaystyle y = zy '}

z=nál nélén+1⋯nál nélj{\ displaystyle z = a_ {i + 1} \ cdots a_ {j}}.

Ha éppen ellenkezőleg , akkor , és mi van , az |x|≥|x′|{\ displaystyle | x | \ geq | x '|}én≥j{\ displaystyle i \ geq j}x=x′z{\ displaystyle x = x'z}y′=zy{\ displaystyle y '= zy}

z=nál nélj+1⋯nál nélén{\ displaystyle z = a_ {j + 1} \ cdots a_ {i}}.

Hosszabbítások

Egyenértékű és osztott monoid

Egy adott ábécé szavainak halmaza, amelyet az összefűzési relációval látunk el, monoidot alkotnak . Levi lemma alkalmazható ezen algebrai szerkezet más példáira is .

Egy monoidot , amelyben Levi lemma áll, egyenértékűnek nevezzük . Az egyenlőség nem garantálja a monoid szabadságát. De a következő tulajdonságunk van:

A monoid szabad, ha és csak akkor, ha equidivisible és ha egyébként van egy morfizmus az adalékanyag monoid természetes egész számok, mint például .M{\ displaystyle M}λ{\ displaystyle \ lambda}M{\ displaystyle M}λ-1(0)={1}{\ displaystyle \ lambda ^ {- 1} (0) = \ {1 \}}

A monoid amely olyan morfizmus a jelzett tulajdonságot nevezzük diplomát , és egy érettségi. Így egy monoid akkor és csak akkor szabad, ha egyenértékű és fokozatos. λ{\ displaystyle \ lambda}λ{\ displaystyle \ lambda}

Egyéb kiterjesztések

Vannak Levi-stílusú lemmák más összefüggésekben, például a gráfelméletben , de a monoidok bizonyos osztályaiban is, például a nyommonoidokban .

A szavak közötti egyenletek

A Levi's lemma az alapösszetevő a szóegyenletek megoldásában. Ebben az összefüggésben a Levi-lemma alkalmazását Nielsen-transzformációnak nevezzük , analóg módon a Nielsen-transzformációval  (in) csoportokban. Például, ha megpróbáljuk megoldani az egyenletet

xu=yv{\ displaystyle xu = yv}

hol és ismeretlen szavak, azt átalakíthatjuk, ha például azt feltételezzük . Ebben az esetben Levi lemma azt mondja, hogy létezik olyan szó , hogy az egyenlet lesz , azaz . Ez a megközelítés lépésről lépésre készít egy grafikont, amely elkészültével lehetővé teszi az egyenlet megoldásának megtalálását. A megoldás általános módját Makanin adta meg. Ezt a módszert azóta jelentősen fejlesztették. x{\ displaystyle x}y{\ displaystyle y}|x|≥|y|{\ displaystyle | x | \ geq | y |}z{\ displaystyle z}x=yz{\ displaystyle x = yz}yzu=yv{\ displaystyle yzu = yv}zu=v{\ displaystyle zu = v}

Történelmi

A lemma Friedrich Wilhelm Levi nevéhez fűződik, aki 1944-ben kiadta.

Megjegyzések és hivatkozások

1. Thierry Lecroq, „  Combinatoire des mots  ” , az Institut d'Électronique et d'Informatique Gaspard-Monge-on . 22. dia.
2. (in) Aldo de Luca és Stefano Varricchio, végesség és szabályosságát félcsoportok és formális nyelvek , Springer Berlin Heidelberg1999( ISBN  978-3-642-64150-3 ) , p.  2.
3. (in) JD McKnight Jr. és AJ Storey , "  Equidivisible semigroups  " , Journal of Algebra , Vol.  12, n o  1,1969. május, P.  24–48 ( DOI  10.1016 / 0021-8693 (69) 90015–5 ).
4. (in) Mr. Lothar, kombinatorika a szavak , Cambridge University Press ,1997, 238  p. ( ISBN  978-0-521-59924-5 , online olvasás ) , p.  13..
5. (in) Elemek az automata elméletről , Cambridge, Cambridge University Press ,2009, 758  p. ( ISBN  978-0-521-84425-3 ) , p.  26..
6. Volker Diekert, „Több mint 1700 év szóegyenlet ” , az Algebrai Informatikai Konferencia Springer, coll.  "Előadási jegyzetek a számítástechnikában" ( n °  9270),2015( ISBN  978-3-319-23020-7 , DOI  10.1007 / 978-3-319-23021-4_2 , arXiv  1507.03215 ) , p.  22–28
7. Friedrich Wilhelm Levi, „  A félcsoportokról  ” , a Kalkuttai Matematikai Társaság Értesítője , t .  36, 1944, P.  141-146.

Kapcsolódó cikk

• Monoid nyom

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">