Kombinatorik på ord

Kombinatorik på ord er en forholdsvis ny inden for matematik, forgrening fra kombinatorik, der fokuserer på studiet af ord og formelle sprog. Emnet ser på bogstaver eller symboler og sekvenserne, de danner. Kombinatorik på ord påvirker forskellige områder af matematisk undersøgelse, herunder algebra og datalogi. Der har været en lang række bidrag til feltet. Nogle af de første arbejde var på kvadrat-fri ord ved Thue i begyndelsen af ​​1900'erne. Han og hans kolleger observerede mønstre i ord og forsøgte at forklare dem. Som tiden gik, kombinatorik på ord blev anvendelig i studiet af algoritmer og kodning. Det førte til udviklingen i abstrakt algebra og besvare åbne spørgsmål.

Definition

Kombinatorik er et område af diskret matematik. Diskret matematik er studiet af tællelige strukturer. Disse objekter har en konkret begyndelse og slutning. Studiet af enumerable objekter er det modsatte af discipliner som analyse, hvor calculus og uendelige strukturer er undersøgt. Kombinatorik undersøgelser hvordan man tælle disse objekter ved hjælp af forskellige repræsentation. Kombinatorik på ord er en nyere udvikling på dette område, som fokuserer på studiet af ord og formelle sprog. En formel sprog er et sæt af symboler og kombinationer af symboler, som folk bruger til at videregive oplysninger.

Nogle terminologi relevant for studiet af ord skal først forklares. Først og fremmest et ord er dybest set en sekvens af symboler eller bogstaver, i et endeligt sæt. En af disse sæt er kendt af den brede offentlighed som alfabetet. For eksempel ordet "Encyclopedia" er en sekvens af symboler i den engelske alfabet, et endeligt sæt af seksogtyve bogstaver. Da et ord kan beskrives som en sekvens, kan anvendes andre basale matematiske beskrivelser. Alfabetet er et sæt, så man kunne forvente, den tomme mængde er en delmængde. Med andre ord findes der et unikt ord med længden nul. Længden af ​​ordet er defineret ved antallet af symboler, der udgør sekvensen, og er betegnet med | w |. Igen ser på eksemplet "encyklopædi", | w | = 12, idet Encyclopedia har tolv breve. Ideen om factoring af store antal kan anvendes til ord, når en faktor af et ord er en blok af på hinanden følgende symboler. Således er "cyklop" er en faktor "Encyclopedia".

Ud over at undersøge sekvenser i sig selv, til et andet område overveje af kombinatorik om ord er, hvordan de kan repræsenteres visuelt. I matematik forskellige strukturer bruges til at kode data. En fælles struktur anvendes i kombinatorik omtales som en træstruktur. En træstruktur er en graf, hvor toppunkterne er forbundet med en linie, der kaldes en sti eller kant. Disse træer kan eller kan ikke indeholde cyklusser, og kan eller kan ikke være komplet. Det er muligt at indkode et ord, idet et ord konstrueres ved symboler og koder dataene ved hjælp et træ. Dette giver en visuel repræsentation af objektet.

Store bidrag

De første bøger om kombinatorik på ord, der opsummerer oprindelsen af ​​emnet blev skrevet af en gruppe matematikere, der kollektivt gik under navnet M. Lothaire. Deres første bog blev udgivet i 1983, da kombinatorik på ord blev mere udbredt.

Mønstre

Mønstre inden ord

En største bidragyder til udviklingen af ​​kombinatorik på ord var Axel Thue; han forsket gentagelse. Thue vigtigste bidrag var bevis for eksistensen af ​​uendelige kvadrat-fri ord. Kvadrat-fri ord ikke har tilstødende faktorer. For at tydeliggøre, "sommer" er ikke firkantet-fri, da m gentages fortløbende, mens "encyklopædi" er firkantet-fri. Thue beviser hans formodninger om eksistensen af ​​uendelige kvadrat-fri ord ved hjælp af erstatninger. En udskiftning er en måde at tage et symbol og erstatte det med et ord. Han bruger denne teknik til at beskrive hans andre bidrag, den Thue-Morse sekvens eller Thue-Morse ord.

Thue skrev to papirer om firkantede-fri ord, hvoraf det andet var på Thue-Morse ord. Marston Morse indgår i navnet, fordi han opdagede det samme resultat som Thue gjorde, men de arbejdede uafhængigt af hinanden. Thue viste sig også, at der findes en overlapning-fri ord. Et overlap-fri ord er, når to symboler x og y, er mønstret xyxyx ikke eksisterer inden for ordet. Han fortsætter i sin anden papir for at bevise en sammenhæng mellem uendelige overlap-fri ord og firkantede-fri ord. Han tager overlap-fri ord, der er skabt ved hjælp af to forskellige bogstaver, og viser, hvordan de kan blive omdannet til firkantede-fri ord af tre bogstaver med substitution. Eugène Prouhet fortsatte med Thue arbejde for at forbedre Thue-Morse ord.

Som tidligere beskrevet, er ord studeret ved at undersøge sekvenserne fra symbolerne. Mønstre findes, og de er i stand til at beskrives matematisk. Mønstre kan enten være undgåelige mønstre eller uundgåelig. En væsentlig bidragsyder til arbejdet i uundgåelige mønstre eller lovmæssigheder, var Frank Ramsey i 1930. Hans vigtige sætning hedder det, at for hele tal k, m≥2 findes der en mindst positivt heltal R sådan, at på trods hvordan en komplet graf er farvet med to farver, vil der altid eksistere en ensfarvet delgraf af hver farve.

Andre bidragsydere til studiet af uundgåelige mønstre omfatter van der Waerden. Hans sætning, at hvis de positive heltal er opdelt i k klasser, så der findes en klasse C, så C indeholder en aritmetisk progression af nogle ukendt længde. En aritmetisk progression er en sekvens af tal, hvor forskellen mellem tilstødende numre forbliver konstant.

Ved behandlingen af ​​uundgåelige mønstre sesquipowers også undersøgt. For nogle mønstre x, y, z, en sesquipower er af formen x, xyx, xyxzxyx, .... Dette er et andet mønster, såsom offentlig-fri, eller uundgåelige mønstre. Coudrain og Schützenbergers primært studeret disse sesquipowers til gruppe teori applikationer. Desuden Zimin bevist, at sesquipowers er alle uundgåelige. Om hele mønsteret dukker op, eller kun en del stykke af sesquipower dukker op gentagne gange, er det ikke muligt at undgå det.

Mønstre inden alfabeter

Halskæder er konstrueret af ord af cirkulære sekvenser. De er oftest bruges i musik og astronomi. Flye Sainte-Marie i 1894 viste sig der er 2-n binære de Bruijn halskæder længde 2. En de Bruijn halskæde indeholder faktorer fremstillet af ord med længden n i et bestemt antal bogstaver. Ordene vises kun én gang i halskæde.

I 1874, Baudot udviklet den kode, der til sidst ville træde i stedet for morsekode ved at anvende teorien om binære de Bruijn halskæder. Problemet fortsatte fra Sainte-Marie til Martin i 1934, som begyndte at se på algoritmer til at gøre ord fra de Bruijn struktur. Det blev derefter arbejdet på af Posthumus i 1943.

Sprog hierarki

Muligvis den mest anvendte resultat i kombinatorik på ord er Chomsky hierarki, som er udviklet af Noam Chomsky. Han studerede formelle sprog i 1950'erne. Hans måde at se på sproget forenklet emnet. Han ser bort fra den egentlige betydning af ordet, ikke overveje visse faktorer såsom frekvens og kontekst, og anvender mønstre af korte vilkår for alle vilkår. Den grundlæggende idé med Chomsky arbejde er at opdele sprog i fire niveauer, eller det sprog hierarki. De fire niveauer er: regelmæssig, kontekst-fri, kontekstafhængig og computably enumerable eller ubegrænset. Regelmæssig er den mindst komplekse mens computably enumerable er det mest komplekse. Mens hans arbejde voksede ud af kombinatorik på ord, det drastisk påvirket andre discipliner, især datalogi.

Word Typer

Sturmian Words

Sturmian ord, skabt af François Sturm, har rødder i kombinatorik på ord. Overvej et ord, der indeholder faktorer længde n. I et Sturmian ord, den faktor med længden n vises præcis n + 1 gange.

Lyndon Word

En Lyndon ord er et ord over et givet alfabet, der er skrevet i sin enkleste og mest beordret form, ud af dens respektive conjugacy klasse. Lyndon ord er vigtige, fordi for en given Lyndon ord x, der findes Lyndon ord y og z, med y & lt; z, x = yz. Endvidere findes der en sætning af Chen, Fox, og Lyndon, at stater enhver Lyndon ord har en unik faktorisering af Lyndon ord, hvor faktoriseringen ord er ikke-stigende. På grund af denne egenskab, er Lyndon ord bruges til at studere algebra, specielt gruppe teori. De danner grundlag for tanken om kommutatorer.

Visuel repræsentation

Cobham bidrog arbejde vedrørende Prouhet arbejde med endelige automater. En matematisk graf er lavet af kanter og knuder. Med endelige automater, er kanterne mærket med et bogstav i et alfabet. For at bruge grafen, man starter på et node og bevæger sig langs kanterne for at nå en endelig knude. Stien taget langs grafen danner ord. Det er et endeligt graf fordi der er en tællelig antal knudepunkter og kanter, og kun én vej forbinder to forskellige knudepunkter.

Gauss-koder, skabt af Carl Friedrich Gauss i 1838, er udviklet ud fra grafer. Specifikt er der behov for en lukket kurve på et fly. Hvis kurven kun krydser over sig selv et endeligt antal gange, så man mærker skæringspunkterne med et brev fra alfabetet brugt. Traveling langs kurven er ordet bestemmes ved at registrere hvert bogstav som et kryds er passeret. Gauss bemærket, at afstanden mellem når det samme symbol dukker op i et ord er et lige heltal.

Gruppe Theory

Walther Franz Anton von Dyck begyndte arbejdet med kombinatorik på ord i gruppe teori ved hans offentliggjorte arbejde i 1882 og 1883. Han begyndte med at bruge ord som gruppens elementer. Lagrange bidrog også i 1771 med hans arbejde med permutation grupper.

Et aspekt af kombinatorik på ord undersøgt i gruppe teori reduceres ord. En gruppe er konstrueret med ord på nogle alfabetet herunder generatorer og inverse elementer, undtagen faktorer, der vises på formen AA eller AA, for nogle et i alfabetet. Dannes Reducerede ord, når de faktorer AA, er AA bruges til at ophæve elementer, indtil en unik ord er nået.

Nielsen transformationer blev også udviklet. For et sæt elementer af en fri gruppe, en Nielsen transformation opnås ved tre transformationer; erstatte et element med dens inverse, der erstatter et element med produktet i sig selv og et andet element, og fjerne ethvert element lig med 1. Ved at anvende disse transformationer Nielsen reducerede sæt dannes. Et reduceret sæt betyder ingen element kan ganges med andre elementer for at annullere helt ud. Der er også forbindelser med Nielsen transformationer med Sturmian ord.

Betragtes problemer

Et problem overvejes i studiet af kombinatorik på ord i gruppe teori er følgende: for to elementer x, y af en semigruppe, gør x = y modulo de definerende relationer x og y. Post og Markov studeret dette problem og bestemt det uafgørbart. Uafgørbar betyder teorien ikke kan bevises.

Det Burnside Spørgsmålet blev bevist ved hjælp af eksistensen af ​​en uendelig kube-fri ord. Dette spørgsmål spørger, om en gruppe, er endelig, hvis koncernen har en konkret antal generatorer og opfylder kriterierne x = 1, for x i gruppen.

Mange ord problemer er uafgørbar baseret på Post korrespondance problemet. Post korrespondance Problemet hedder for substitutioner x og y kortlægning fra nogle alfabetet A til nogle alfabet B, gør der eksisterer et ord m i A, således at x = y? Indlæg fastslået, at dette problem er uafgørbart, således når ord problemer er reduceret til det grundlæggende problem, kan de bestemmes samt at være uafgørbar.

Andre anvendelser

Kombinatorik på ord har applikationer på ligninger. Makanin bevist, at det er muligt at finde en løsning for et begrænset ligningssystem, når ligningerne er konstrueret af ord.

  0   0
Forrige artikel CEFIC

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha