Combinatori di parole

La combinazione delle parole è una branca della matematica e dell'informatica teorica che applica alla combinatoria le parole finito o infinito. Questo ramo si è sviluppato da diversi rami della matematica: teoria dei numeri , teoria dei gruppi , probabilità e, naturalmente, combinatoria . Ha collegamenti con vari argomenti informatici, come algoritmi di testo , ricerca di pattern e compressione di testo.

Campi di studio e applicazioni

L'oggetto della combinatoria delle parole sono le proprietà di parole finite o particolari parole infinite . Questo è da paragonare alla teoria dei linguaggi formali , che si interessa di insiemi di parole, in vista della loro rappresentazione e analisi.

Per una classe di parole, lo studio si concentra su caratterizzazioni equivalenti, proprietà combinatorie, enumerazione, enumerazione sistematica o generazione casuale. Studiamo anche gli algoritmi e la loro efficienza per l'effettiva realizzazione di queste operazioni.

La combinatoria delle parole trova applicazioni in vari campi dell'informatica teorica , come la teoria degli automi e la linguistica . Lo sviluppo del testo digitale e dell'elaborazione di testi ha portato a importanti sviluppi nella combinatoria delle parole. È presente alla base di algoritmi di testo, linguaggio naturale trattamento automatico , l'elaborazione vocale e bioinformatica .

Storico

La combinazione delle parole indietro al lavoro di Axel Thue sui simboli follow non ripetitivi agli inizi del XX °  secolo. I lavori principali, negli anni successivi, sono quelli di Marston Morse e dei suoi coautori sulla continuazione di Prouhet-Thue-Morse e le parole di Sturmian . Una famosa applicazione della combinatoria delle parole è l'uso che si fa di una sequenza senza ripetizione nella risposta negativa alla congettura di Burnside data da Piotr Novikov e Adian .

È Marcel-Paul Schützenberger il fondatore della moderna combinatoria delle parole, in particolare nei lavori con Roger C. Lyndon e André Lentin . I suoi corsi sono stati scritti da Jean-François Perrot e hanno dato vita al libro “Combinatorics on words”, un'opera collettiva firmata dallo pseudonimo M. Lothaire , e pubblicata nel 1983. La combinatoria delle parole si è sviluppata rapidamente da questa data. Altri due libri di sintesi, firmati Lothaire, compaiono in seguito, e diverse opere collettive prendono il loro seguito.

Temi

Le parole di Lyndon

Le parole di Lyndon , così chiamate dal matematico Roger Lyndon , sono parole primitive e minimali nella loro combinazione di classe. Uno dei risultati di base è che ogni parola ammette una singola fattorizzazione decrescente nelle parole di Lyndon (risultato erroneamente attribuito a Chen, Fox e Lyndon). Un altro risultato notevole è che il prodotto, in ordine crescente, delle parole di Lyndon la cui lunghezza divide un dato intero è una parola di de Bruijn .

Prove

La combinatoria delle parole si occupa in particolare di descrivere le condizioni in cui compaiono le ripetizioni nelle parole ( parole senza quadrati , tra le altre), la costruzione o trasformazione delle parole, per morfismo . Un caso più generale è coperto dalla nozione di ragione inevitabile o dal suo opposto, ragioni evitabili . Ad esempio, lo "schema" (dove e sono simboli) denota la presenza, in una parola, di un fattore della forma (dove questa volta e sono parole). Dire che una parola evita questo schema è che non contiene questo fattore. Dire che un pattern è inevitabile significa dire che qualsiasi parola sufficientemente lunga contiene un fattore della forma descritta dal pattern. Lo schema è inevitabile, lo schema è evitabile, anche su due lettere. XsìXsìX{\ displaystyle xyxyx}X{\ stile di visualizzazione x}sì{\ stile di visualizzazione y}tuvtuvtu{\ displaystyle uvuvu}tu{\ displaystyle u}v{\ stile di visualizzazione v}XsìX{\ stile di visualizzazione xyx}XsìXsìX{\ displaystyle xyxyx}

La nozione di ripetizione è estesa alle ripetizioni frazionarie come segue: il periodo (detto anche periodo minimo ) di una parola è il più piccolo intero come per . L' esponente della parola è il quoziente della sua lunghezza per il suo periodo. Ad esempio, la parola ha il periodo 3, ha l'esponente 7/3. L' esponente critico di una parola infinita, che è il più grande esponente di un fattore nella parola, dipende dalla natura della parola. Un tema simile è la copertura di una parola con un motivo; le parole che ammettono tale copertura sono chiamate parole quasi-periodiche . w=a1⋯anon{\ displaystyle w = a_ {1} \ cdots a_ {n}}p{\ stile di visualizzazione p}aio=ap+io{\ displaystyle a_ {i} = a_ {p + i}}io=1,...,non-p{\ displaystyle i = 1, \ ldots, np}w{\ stile di visualizzazione w}non/p{\ stile di visualizzazione n/p}entente

L'esistenza di una soglia per le ripetizioni frazionarie è stata ipotizzata da Françoise Dejean nel 1972; la prova di questo fatto è il teorema di Dejean .

La nozione di ripetizione è estesa anche alle cosiddette ripetizioni abeliane: quindi un quadrato abeliano è una parola dove è un anagramma di , cioè uguale fino a una permutazione delle lettere; per esempio è un quadrato abeliano. Possiamo mostrare che i cubi abeliani possono essere evitati su 3 lettere, ma i quadrati abeliani sono evitabili solo su 4 lettere. Xsì{\ stile di visualizzazione xy}sì{\ stile di visualizzazione y}X{\ stile di visualizzazione x}X{\ stile di visualizzazione x}abba{\ displaystyle abba}

Una ripetizione massima (in inglese a run ) in una parola è un fattore di esponente di almeno 2 e che non può essere esteso a una ripetizione più lunga. Il numero totale di ripetizioni massime in una parola di lunghezza è al massimo uguale a . Questo risultato, chiamato teorema delle ripetizioni massime , detto anche “teorema delle serie”, è stato dimostrato nel 2015. non{\ stile di visualizzazione n}non{\ stile di visualizzazione n}

Parole senza quadrati e senza poteri

Un quadrato è una parola composta da due parti uguali consecutive, come "caramella" o "papà". In bioinformatica , un quadrato è chiamato ripetizione in tandem . Una parola senza quadrato è una parola che non contiene un fattore quadrato. Ad esempio, la parola "consecutivamente" è una parola senza quadrato. Più in generale, una parola senza cubo e una parola senza una potenza -esima è una parola che non contiene un cubo o una potenza fattore-esima. Ci sono infinite parole senza quadrati su qualsiasi alfabeto di almeno tre lettere, come dimostrato da Axel Thue . Su un alfabeto di due lettere, una parola del genere non esiste. La parola di Prouhet-Thue-Morse contiene quadrati, d'altra parte è senza cubo. K{\ stile di visualizzazione k}K{\ stile di visualizzazione k}

Complessità combinatoria di una parola

Esistono diversi modi per comprendere la complessità di una serie infinita di simboli. Intuitivamente, queste nozioni dovrebbero indicare fino a che punto una sequenza è "complicata" o "complessa", o "casuale" o "caotica". La complessità computazionale è una misura che valuta quanto sia difficile costruire. Questa difficoltà è misurata dalla dimensione del programma necessaria per costruirlo, o dal tempo necessario per calcolarne l' ennesimo termine. La teoria dell'informazione algoritmica fondata da Kolmogorov , Solomonoff e Chaitin affronta questi problemi. La complessità di Kolmogorov di una sequenza è la dimensione del programma più breve su una macchina di Turing che genera quella sequenza. La nozione è anche correlata alla comprimibilità di una sequenza.

Un'altra misura, più aritmetica o combinatoria, è la complessità “in factor”, in inglese “  subword complex  ” , detta anche complessità combinatoria . Misura il numero di fattori che una parola ha per ogni lunghezza. Formalmente, la funzione di complessità di una parola finita o infinita è la funzione che, per ogni intero , conta il numero di fattori (o blocchi) di lunghezza in questa parola. Per una parola infinita , un risultato dovuto a Ethan M. Coven e Gustav Hedlund dice che se per un numero intero , allora la parola è in definitiva periodica. Le parole infinite aperiodiche di minima complessità hanno quindi una funzione di complessità pari a . Queste sono le parole di Sturmian . La più nota delle parole sturmiane è la parola di Fibonacci . Le misure correlate sono la complessità palindromica che misura il numero di palindromi o la complessità aritmetica . X{\ stile di visualizzazione x}non↦vsX(non){\ displaystyle n \ mapsto c_ {x} (n)}non{\ stile di visualizzazione n}vsX(non){\ displaystyle c_ {x} (n)}non{\ stile di visualizzazione n}X{\ stile di visualizzazione x}vsX(non)≤non{\ displaystyle c_ {x} (n) \ leq n}non{\ stile di visualizzazione n}X{\ stile di visualizzazione x}non+1{\ stile di visualizzazione n + 1}

Il termine “complessità combinatoria”, in opposizione alla complessità algoritmica, è piuttosto recente: lo troviamo ad esempio con Jean-Paul Allouche o Michel Rigo.

Parole automatiche

Le parole automatiche sono sequenze che possono essere impostate utilizzando degli automi finiti . La suite Prouhet-Thue-Morse è l'esempio paradigmatico di questa famiglia. Le pieghe della carta sono un altro esempio.

parole morfiche

Una parola morfica è una parola infinita ottenuta dall'iterazione di un morfismo, seguita dall'applicazione di un secondo morfismo. In assenza del secondo morfismo, si parla di una parola puramente morfica . È un metodo molto efficace e diffuso per costruire parole infinite. È "robusto" nel senso che è stabile per tutti i tipi di operazioni. Ad esempio, la parola infinita di Fibonacci è una parola puramente morfica, così come la sequenza Prouhet-Thue-Morse . La sequenza caratteristica dei quadrati:1100100010000001000... è morfico, ma non è puramente morfico.

Complessità abeliana

La complessità abeliana di una parola finita o infinita è la funzione che conta il numero dei fattori di lunghezza dati in questa parola, fino alla permutazione delle lettere. Questa è un'altra misura della complessità combinatoria di una sequenza.

Equazioni tra le parole

Un'equazione parola o un equazione tra parole (in inglese equazione parola ) è una coppia di parole , di solito scritta nella forma di un'equazione (tu,V){\ stile di visualizzazione (U, V)}

tu=V{\ stile di visualizzazione U = V}.

Qui, e sono parole composte da lettere che sono costanti o variabili. Le costanti sono scritte in minuscolo, le variabili in maiuscolo. Ad esempio, l'equazione tu{\ stile di visualizzazione U}V{\ stile di visualizzazione V}

abXbX=XbXba{\ displaystyle abXbX = XbXba}

contiene quattro occorrenze della variabile e le costanti e . Una soluzione di un'equazione è un insieme di parole senza variabili, una per ogni variabile, in modo tale che la sostituzione delle parole con le variabili rende uguali le due componenti dell'equazione. Ad esempio, per (e più in generale per con , entrambi i membri dell'equazione diventano uguali, a (e più in generale a ). X{\ stile di visualizzazione X}a{\ stile di visualizzazione a}b{\ stile di visualizzazione b}X=a{\ stile di visualizzazione X = a}X=(ab)Ka{\ displaystyle X = (ab) ^ {k} a}K≥0{\ displaystyle k \ geq 0}ababa{\ displaystyle ababa}(ab)2K+2a{\ stile di visualizzazione (ab) ^ {2k + 2} a}

Un famoso teorema di Makanin dice che è decidibile se un'equazione di parole, e più in generale un insieme di equazioni di parole, ha una soluzione. In questo, le equazioni di parole si distinguono dalle equazioni diofantee per le quali l'esistenza di soluzioni è indecidibile dal teorema di Matiassevitch che risolve il decimo problema di Hilbert .

Un problema correlato è la descrizione di tutte le soluzioni di una data equazione, solitamente in forma parametrizzata. Il primo studio sistematico in questa direzione è di Hmelevskii.

ricorrenza

Una parola infinita è ricorrente se un qualsiasi fattore di appare infinite volte in . X{\ stile di visualizzazione x}X{\ stile di visualizzazione x}X{\ stile di visualizzazione x}

• La parola non è ricorrente.abω{\ displaystyle ab ^ {\ omega}}
• La parola Champernowne binaria0100011011000001010011...{\ displaystyle 0100011011000001010011 \ ldots} formato dalla concatenazione di espansioni binarie di interi naturali è ricorrente.
• Una parola in definitiva periodica e ricorrente è periodica.

Una parola infinita è uniformemente ricorrente o con spazi limitati se due occorrenze consecutive di un fattore di sono a distanza limitata. Più precisamente, per ogni fattore di , esiste una costante tale che due occorrenze consecutive di in siano al più remote . X{\ stile di visualizzazione x}X{\ stile di visualizzazione x}tu{\ displaystyle u}X{\ stile di visualizzazione x}NON(tu){\ stile di visualizzazione N (u)}tu{\ displaystyle u}X{\ stile di visualizzazione x}NON(tu){\ stile di visualizzazione N (u)}

• La parola binaria Champernowne non è uniformemente ricorrente. Infatti, due occorrenze consecutive del simbolo possono essere separate da sequenze arbitrariamente lunghe di .1{\ stile di visualizzazione 1}0{\ stile di visualizzazione 0}
• La parola di Fibonacci 010010100100101001010...{\ displaystyle 010010100100101001010 \ ldots}è uniformemente ricorrente. Ad esempio, le occorrenze del numero in questa parola infinito sono gli elementi della sequenza A001950 del OEIS , vale a dire 2, 5, 7, 10, 13, 15, 18, ... La distanza tra due quelli consecutivi è quindi al massimo 3.1{\ stile di visualizzazione 1}1{\ stile di visualizzazione 1}
• La parola Thue-Morse è uniformemente ricorrente.

C'è un legame tra le parole uniformemente ricorrenti e gli insiemi sindetici . Un insieme di interi naturali si dice sindetico se esiste un intero tale che per due interi consecutivi di , si ha . Una parola infinita è quindi uniformemente ricorrente se, per qualsiasi fattore di , l'insieme degli inizi di occorrenza di in è sindetico. S{\ stile di visualizzazione S}NON{\ stile di visualizzazione N}S<t{\ displaystyle s <t}S{\ stile di visualizzazione S}t-S<NON{\ stile di visualizzazione ts <N}X{\ stile di visualizzazione x}tu{\ displaystyle u}X{\ stile di visualizzazione x}S(tu){\ stile di visualizzazione S (u)}tu{\ displaystyle u}X{\ stile di visualizzazione x}

La funzione di ricorrenza di una parola infinita fornisce il valore massimo degli spazi tra occorrenze consecutive di parole di una data lunghezza. Più precisamente, è il più piccolo intero tale che ogni fattore di lunghezza è un fattore di qualsiasi fattore di lunghezza di , formalmenteR{\ stile di visualizzazione R}X{\ stile di visualizzazione x}R(non){\ stile di visualizzazione R (n)}NON{\ stile di visualizzazione N}X{\ stile di visualizzazione x}non{\ stile di visualizzazione n}NON{\ stile di visualizzazione N}X{\ stile di visualizzazione x}R(non)=inf{NON|∀w∈FNON(X),Fnon(w)=Fnon(X)}{\ displaystyle R (n) = \ inf \ {N \ mid \ forall w \ in F_ {N} (x), F_ {n} (w) = F_ {n} (x) \}} Possiamo vedere l'intero come la larghezza minima di una finestra che facciamo scorrere sulla parola e che ha la proprietà che qualsiasi fattore di lunghezza appare sempre nella sezione coperta dalla finestra. R(non){\ stile di visualizzazione R (n)}X{\ stile di visualizzazione x}non{\ stile di visualizzazione n}

• Per la parola di Fibonacci abbiamo , e ; infatti, il fattore della parola di Fibonacci non contiene il fattore , ma qualsiasi fattore di lunghezza 6 contiene i tre fattori perché non è un fattore della parola di Fibonacci.R(1)=3{\ stile di visualizzazione R (1) = 3}R(2)=6{\ stile di visualizzazione R (2) = 6}01010{\ stile di visualizzazione 01010}00{\ stile di visualizzazione 00}00,01,10{\ stile di visualizzazione 00,01,10}10101{\ displaystyle 10101}

Funzione di ricorrenza della sequenza Prouhet-Thue-Morse

Per la parola Thue-Morse , abbiamo (qualsiasi fattore di lunghezza 3 contiene uno e uno ) e (il fattore non contiene ). Infatti, la funzione di ricorrenza è stata calcolata da Morse e Hedlund, già nel 1938. I primi valori sono riportati nella seguente tabella: 01101001100101101001...{\ displaystyle 01101001100101101001 \ ldots}R(1)=3{\ stile di visualizzazione R (1) = 3}0{\ stile di visualizzazione 0}1{\ stile di visualizzazione 1}R(2)=9{\ stile di visualizzazione R (2) = 9}01011010{\ stile di visualizzazione 01101010}11{\ stile di visualizzazione 11}

Funzione di ricorrenza della sequenza Prouhet-Thue-Morse

non{\ stile di visualizzazione n}	1	2	3	4	5	6	7	8	9	10
R(non){\ stile di visualizzazione R (n)}	3	9	11	21	22	41	42	43	44	81

Questo è il risultato A179867 di OEIS . La formula di ricorrenza è abbastanza semplice: per , abbiamonon≥2{\ displaystyle n \ geq 2}R(2non)=2R(non+1)-1{\ stile di visualizzazione R (2n) = 2R (n + 1) -1} R(2non+1)=2R(non+1){\ stile di visualizzazione R (2n + 1) = 2R (n + 1)}. Ciò si traduce nella seguente forma chiusa. Mettiamo in posa , con . Tale scrittura è sempre possibile per . Alloranon=2r+p{\ stile di visualizzazione n = 2 ^ {r} + p}2≤p≤2r+1{\ displaystyle 2 \ leq p \ leq 2 ^ {r} +1}non≥3{\ displaystyle n \ geq 3}R(non)=10⋅2r+p-1{\ displaystyle R (n) = 10 \ cdot 2 ^ {r} + p-1}.

Funzione di induzione di parole infinite di Fibonacci

Questa funzione di ricorrenza ha un'espressione un po' meno semplice ed è nota dall'articolo di Morse e Hedlund nel 1940. Abbiamo R(non)=FNON+1+FNON+non-1{\ stile di visualizzazione R (n) = F_ {N + 1} + F_ {N} + n-1}dove è l'intero tale che . Ecco i numeri di Fibonacci con . NON{\ stile di visualizzazione N}FNON≤non<FNON+1{\ displaystyle F_ {N} \ leq n <F_ {N + 1}}FNON{\ stile di visualizzazione F_ {N}}F0=0,F1=1{\ stile di visualizzazione F_ {0} = 0, F_ {1} = 1}

Funzione di induzione di parole infinite di Fibonacci

non{\ stile di visualizzazione n}	1	2	3	4	5	6	7	8	9	10
R(non){\ stile di visualizzazione R (n)}	3	6	10	11	17	18	19	28	29	30

E ' l'A183545 Suite del OEIS . Questa formula si estende a tutte le parole sturmiane .

Note e riferimenti

(fr) Questo articolo è parzialmente o interamente tratto dall'articolo di Wikipedia in inglese intitolato “  Combinatoria sulle parole  ” ( vedi l'elenco degli autori ) .

1. FM Dekking , “  Sequenze fortemente non ripetitive e set privi di progressione  ”, Journal of Combinatorial Theory, Series A , vol.  27, n .  21979, pag.  181-185 ( ISSN  0097-3165 , DOI  10.1016 / 0097-3165 (79) 90044-X )
2. Veikko Keränen , “  I quadrati abeliani sono evitabili su 4 lettere  ”, Automi, Linguaggi e Programmazione. ICAP ,1992, pag.  41–52 ( ISSN  0302-9743 , DOI  10.1007 / 3-540-55719-9_62 ).
3. Jean-Paul Allouche, “  Rilievo di alcune nozioni di complessità per successioni finite e infinite  ”, Funzioni in teoria dei numeri e loro aspetti probabilistici , Kyoto, Ris. ist. Matematica. Sci. (CERCHI),2012, pag.  27-37 ( Recensioni di matematica  MR3014836 , leggi online ).
4. Michel Rigo, Linguaggi formali, automi e sistemi di numerazione , vol.  1, John Wiley & Figli,2014, 336  pag. ( ISBN  978-1-84821-615-0 e 1848216157 ).
5. Makanin 1977 .
6. Diekert 2002 .
7. Hmelevskii 1976 .
8. Allouche & Shallit (2003), pagine 328-331, e Morse & Hedlund (1938), pagine 834-839.

Vedi anche

Articoli Correlati

• Metrica delle parole
• Problema con le parole
• Teorema della periodicità di Fine e Wilf

Bibliografia

Storia

• Jean Berstel e Dominique Perrin , “  Le origini della combinatoria sulle parole  ”, European Journal of Combinatorics , vol.  28,2007, pag.  996–1022 ( leggi online ).
• Dominique Perrin , "  Gli inizi della combinatoria delle parole  ", seminario EHESS ,2005( leggi in linea ).

Rivedi gli articoli

• [1992] Klaus Ulrich Schulz (a cura di), Equazioni di parole e argomenti correlati , Springer-Verlag,1992, 256  pag. ( ISBN  978-3-540-55124-9 , leggi online ) - Atti della conferenza IWWERT '90, Tübingen, Germania, 1-3 ottobre 1990
• [1997] Christian Chhoffrut e Juhani Karhumäki, “Combinatori di parole” , in G. Rozenberg, A. Salomaa (a cura di), Handbook of Formal Languages , vol.  1: Parola, Lingua, Grammatica , Springer Verlag,1997( ISBN  978-3-540-60420-4 , presentazione online ) , p.  329-438
• [2002] Volker Diekert, cap.  12 “Algoritmo di Makanin” , in M. Lothaire, Combinatoria algebrica sulle parole , Cambridge University Press, coll.  "Enciclopedia della matematica e delle sue applicazioni" ( n o  90)2002, pag.  387-442.
• [2003] Jean Berstel e Juhani Karhumäki , “  Combinatoria sulle parole - un tutorial  ”, Bull. Euro. Assoc. Teore. Calcola. Sci. (EATCS) , vol.  79,2003, pag.  178-228 ( leggi in linea ).
• [2004] Juhani Karhumäki , "  Combinatoria sulle parole: un nuovo argomento stimolante  " TUCS Technical Report , n o  645,2004( leggi in linea ).
• [2015] Dominique Perrin e Antonio Restivo , “Words” , in Miklos Bona (a cura di), Handbook of Enumerative Combinatoric , Chapman e Hall / CRC,2015, 1086  pag. ( ISBN  9781482220865 , presentazione online , leggi online )

Lotario

• M. Lothaire , Combinatoria sulle parole , Cambridge University Press, coll.  "Biblioteca matematica di Cambridge",1997, xviii + 238  p. ( ISBN  978-0-521-59924-5 , DOI  10.1017 / CBO9780511566097 , Math Review  1475463 , presentazione online )
• M. Lothaire , Combinatoria algebrica sulle parole , Cambridge University Press , coll.  "Enciclopedia della matematica e delle sue applicazioni" ( n o  90)2002, 504  pag. ( ISBN  978-0-521-81220-7 , presentazione online )
• (it) M. Lothaire , Combinatoria applicata alle parole , Cambridge (GB), Cambridge University Press , coll.  "Enciclopedia della matematica e delle sue applicazioni" ( n o  105)2005, 610  pag. ( ISBN  978-0-521-84802-2 , presentazione online )

Berthé - Rigo

• Valérie Berthé e Michel Rigo (a cura di), Sequenze, gruppi e teoria dei numeri , Birkhäuser, coll.  "Tendenze in matematica",2018, XXVI + 576  pag. ( ISBN  978-3-319-69151-0 )
• Valérie Berthé e Michel Rigo (a cura di), Combinatoria, parole e dinamiche simboliche , Cambridge, Regno Unito, Cambridge University Press, coll.  "Enciclopedia della matematica e delle sue applicazioni" ( n o  159)marzo 2016, 496  pag. ( ISBN  978-1-107-07702-7 )
• Valérie Berthé e Michel Rigo (a cura di), Combinatoria, automi e teoria dei numeri , Cambridge University Press, coll.  "Enciclopedia della matematica e delle sue applicazioni" ( n o  135)2010, 615  pag. ( ISBN  978-0-521-51597-9 , leggi online )

Monografie

• (it) Jean-Paul Allouche e Jeffrey O. Shallit , Sequenze automatiche: teoria, applicazioni, generalizzazioni , Cambridge, Cambridge University Press,2003, 571  pag. ( ISBN  0-521-82332-3 , Recensioni di matematica  1997038 , zbMATH  1086.11015 )
• Maxime Crochemore e Wojciech Rytter, Jewels of stringology: Text Algorithms , World Scientific Publishing,2002, 310  pag. ( ISBN  978-981-02-4897-0 , leggi online )
• Maxime Crochemore, Thierry Lecroq e Wojciech Rytter, 125 problemi negli algoritmi di testo con soluzioni , Cambridge University Press,2021, 345  pag. ( ISBN  978-1-108-83583-1 e 978-1-108-79885-3 )
• .

Testi storici

• Giu. I. Hmelevskii, Equations in free semigroups , American Mathematical Society, Proceedings of the Steklov Institute of Mathematics 107 (1971),1976, 270  pag. ( ISBN  978-0-8218-3007-9 , Math Recensioni  0393284 , zbMATH  0326.02032 , presentazione online ) - Tradotto dall'originale russo, pubblicato nel 1971, da GA Kandall.

• Gennadiy S. Makanine, "  Il problema della risolvibilità delle equazioni in un semigruppo libero  ", Math. Sbornik (NS) , vol.  103, n .  21977, pag.  147-236, 319 ( Recensioni di matematica  0470107 )- Articolo completo, in russo. Traduzione inglese: matematica. URSS Sbornik 32 (1977)

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