24:
224:. This approach results in a graph of substitutions generated by repeatedly applying Levi's lemma. If each unknown appears at most twice, then a word equation is called quadratic; in a quadratic word equation the graph obtained by repeatedly applying Levi's lemma is finite, so it is
275:
of strings and string concatenation has this property (by Levi's lemma for strings), but by itself equidivisibility is not enough to guarantee that a monoid is free. However an equidivisible monoid
358:
662:
633:
608:
583:
526:
683:
390:
44:
471:
654:
60:
233:
364:
simply being a homomorphism does not guarantee this latter property, as there could be multiple elements of
410:
173:
153:
52:
305:
17:
483:
291:
165:
152:
that is "in the middle", and can be grouped to one side or the other. Levi's lemma is named after
571:
451:(1968), "A connection between systems of word and length equations and Hilbert's tenth problem",
658:
629:
604:
579:
522:
448:
385:
260:
originally due to
Christine Duboc. Several proofs of Levi's Lemma for traces can be found in
551:
491:
430:
225:
426:
688:
434:
422:
487:
513:
229:
677:
556:
253:
495:
280:
257:
249:
508:
272:
48:
542:
Duboc, Chr. (1986), "On some equations in free partially commutative monoids",
23:
368:
mapped to 0.) A monoid for which such a homomorphism exists is also called
295:
474:(1977), "The problem of solvability of equations in a free semigroup",
482:(2), English transl. in Math. USSR Sbornik 32 (1977): 147–236,
453:
Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI)
601:
Finiteness and
Regularity in Semigroups and Formal Languages
653:, Translated from the French by Reuben Thomas, Cambridge:
294:(free monoid on one generator) with the property that the
267:
A monoid in which Levi's lemma holds is said to have the
164:
Levi's lemma can be applied repeatedly in order to solve
256:; for example, there is a more general Levi lemma for
232:. A more general method for solving word equations is
308:
512:
352:
248:; the lemma can occur in a more general form in
192:are the unknowns, we can transform it (assuming
168:; in this context it is sometimes called the
415:Bulletin of the Calcutta Mathematical Society
8:
347:
334:
298:of 0 contains only the identity element of
628:. Cambridge University Press. p. 13.
603:. Springer Berlin Heidelberg. p. 2.
599:Aldo de Luca; Stefano Varricchio (1999).
555:
341:
313:
307:
176:. For example, starting with an equation
22:
16:For the statement in real analysis, see
402:
279:is free if additionally there exists a
7:
578:. World Scientific. pp. 1–576.
353:{\displaystyle f^{-1}(0)=\{1_{M}\}}
14:
174:Nielsen transformation for groups
519:Algebraic Combinatorics on Words
496:10.1070/SM1977v032n02ABEH002376
521:. Cambridge University Press.
391:String functions (programming)
328:
322:
1:
649:Sakarovitch, Jacques (2009),
228:if a quadratic word equation
86:, then there exists a string
557:10.1016/0304-3975(86)90028-9
544:Theoretical Computer Science
156:, who published it in 1944.
51:, especially in the area of
45:theoretical computer science
651:Elements of automata theory
148:That is, there is a string
705:
655:Cambridge University Press
244:The above is known as the
15:
413:(1944), "On semigroups",
292:monoid of natural numbers
269:equidivisibility property
376:is called a gradation).
684:Combinatorics on words
626:Combinatorics on Words
354:
246:Levi lemma for strings
170:Nielsen transformation
154:Friedrich Wilhelm Levi
53:combinatorics on words
40:
355:
59:states that, for all
26:
624:M. Lothaire (1997).
449:Matiyasevich, Yu. V.
306:
172:by analogy with the
39:case of Levi's lemma
488:1977SbMat..32..129M
234:Makanin's algorithm
576:The Book of Traces
572:Grzegorz Rozenberg
350:
262:The Book of Traces
196:, so there exists
41:
35:and v =
18:Beppo Levi's lemma
664:978-0-521-84425-3
635:978-0-521-59924-5
610:978-3-642-64150-3
386:String operations
90:such that either
696:
668:
667:
646:
640:
639:
621:
615:
614:
596:
590:
589:
570:Volker Diekert;
567:
561:
560:
559:
539:
533:
532:
516:
505:
499:
498:
468:
462:
460:
445:
439:
437:
407:
359:
357:
356:
351:
346:
345:
321:
320:
95:uw = x
704:
703:
699:
698:
697:
695:
694:
693:
674:
673:
672:
671:
665:
648:
647:
643:
636:
623:
622:
618:
611:
598:
597:
593:
586:
574:, eds. (1995).
569:
568:
564:
541:
540:
536:
529:
507:
506:
502:
470:
469:
465:
447:
446:
442:
409:
408:
404:
399:
382:
337:
309:
304:
303:
242:
240:Generalizations
162:
21:
12:
11:
5:
702:
700:
692:
691:
686:
676:
675:
670:
669:
663:
657:, p. 26,
641:
634:
616:
609:
591:
584:
562:
534:
527:
500:
472:Makanin, G. S.
463:
440:
401:
400:
398:
395:
394:
393:
388:
381:
378:
349:
344:
340:
336:
333:
330:
327:
324:
319:
316:
312:
241:
238:
230:has a solution
166:word equations
161:
158:
146:
145:
115:
114:
13:
10:
9:
6:
4:
3:
2:
701:
690:
687:
685:
682:
681:
679:
666:
660:
656:
652:
645:
642:
637:
631:
627:
620:
617:
612:
606:
602:
595:
592:
587:
585:981-02-2058-8
581:
577:
573:
566:
563:
558:
553:
549:
545:
538:
535:
530:
528:0-521-81220-8
524:
520:
515:
510:
504:
501:
497:
493:
489:
485:
481:
477:
473:
467:
464:
458:
454:
450:
444:
441:
436:
432:
428:
424:
420:
416:
412:
406:
403:
396:
392:
389:
387:
384:
383:
379:
377:
375:
371:
367:
363:
360:. (Note that
342:
338:
331:
325:
317:
314:
310:
301:
297:
293:
289:
285:
282:
278:
274:
270:
265:
263:
259:
255:
254:monoid theory
251:
247:
239:
237:
235:
231:
227:
223:
219:
215:
211:
207:
203:
199:
195:
191:
187:
183:
179:
175:
171:
167:
159:
157:
155:
151:
143:
139:
135:
132: =
131:
127:
124: =
123:
120:
119:
118:
112:
108:
104:
101: =
100:
96:
93:
92:
91:
89:
85:
82: =
81:
77:
73:
69:
65:
62:
58:
54:
50:
46:
38:
34:
31: =
30:
25:
19:
650:
644:
625:
619:
600:
594:
575:
565:
547:
543:
537:
518:
503:
479:
476:Mat. Sbornik
475:
466:
456:
452:
443:
418:
414:
405:
373:
369:
365:
361:
299:
287:
283:
281:homomorphism
276:
268:
266:
261:
250:graph theory
245:
243:
221:
217:
213:
209:
205:
201:
197:
193:
189:
185:
181:
177:
169:
163:
160:Applications
149:
147:
141:
137:
133:
129:
125:
121:
116:
110:
106:
102:
98:
94:
87:
83:
79:
75:
71:
67:
63:
56:
42:
36:
32:
28:
550:: 159–174,
509:M. Lothaire
421:: 141–146,
411:Levi, F. W.
273:free monoid
49:mathematics
678:Categories
435:0061.02405
216:, thus to
200:such that
57:Levi lemma
459:: 132–144
372:(and the
315:−
226:decidable
194:|x| ≥ |y|
511:(2002).
380:See also
296:preimage
484:Bibcode
427:0011694
302:, i.e.
290:to the
252:and in
61:strings
689:Lemmas
661:
632:
607:
582:
525:
433:
425:
370:graded
271:. The
258:traces
184:where
55:, the
397:Notes
286:from
208:) to
140:| ≥ |
136:(if |
109:| ≤ |
105:(if |
78:, if
659:ISBN
630:ISBN
605:ISBN
580:ISBN
523:ISBN
514:"12"
188:and
128:and
97:and
74:and
47:and
27:The
552:doi
492:doi
480:103
431:Zbl
210:ytα
117:or
43:In
680::
548:46
546:,
517:.
490:,
478:,
455:,
429:,
423:MR
419:36
417:,
264:.
236:.
220:=
218:tα
214:yβ
212:=
206:yt
182:yβ
180:=
178:xα
144:|)
130:wv
126:xw
113:|)
103:wy
84:xy
80:uv
70:,
66:,
37:wy
29:uw
638:.
613:.
588:.
554::
531:.
494::
486::
461:.
457:8
438:.
374:f
366:M
362:f
348:}
343:M
339:1
335:{
332:=
329:)
326:0
323:(
318:1
311:f
300:M
288:M
284:f
277:M
222:β
204:=
202:x
198:t
190:y
186:x
150:w
142:x
138:u
134:y
122:u
111:x
107:u
99:v
88:w
76:y
72:x
68:v
64:u
33:x
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
