Słowo parametru

W matematycznym badaniu kombinatoryki na słowach słowo parametryczne to ciąg nad danym alfabetem zawierający pewną liczbę znaków wieloznacznych . Zestaw łańcuchów pasujących do danego słowa parametru nazywany jest zestawem parametrów lub kostką kombinatoryczną . Słowa parametrów można komponować w celu wytworzenia mniejszych podsześcianów danej kostki kombinatorycznej. Mają zastosowanie w teorii Ramseya iw informatyce do wykrywania duplikatów kodu .

Definicje i notacja

Formalnie, słowo $k$ parametru o długości nad danym alfabetem $jest$ sekwencją znaków, z $k$ niektóre można narysować za $}$ od ${\ Displaystyle A},$ a pozostałe to $wieloznaczne$ symbole ${\ Displaystyle * _ {1}, * _ {2}, \ ldots, * _ {k}}$ . Każdy symbol wieloznaczny musi pojawić się co najmniej raz, ale może pojawić się wiele razy, a znaki wieloznaczne muszą pojawiać się w kolejności określonej przez ich indeksy: pierwszy znak wieloznaczny w słowie musi być ∗ 1 {\ displaystyle ${1} }$ , następny, który różni się od ${\ Displaystyle * _ {1}}$ musi być ${\ Displaystyle * _ {2}}$ , itd. W szczególnym przypadku słowo nad danym alfabetem, bez żadnych symboli wieloznacznych, jest uważane za słowo z parametrem 0. W przypadku słów 1-parametrowych indeksy dolne można pominąć, ponieważ nie ma dwuznaczności między różnymi symbolami wieloznacznymi. Zbiór wszystkich $słów$ { nad oznaczony $}}$ . o długości , jest $Displaystyle$$A {\ tbinom {n}$$k$

A ${\ displaystyle k} - słowo$ parametru reprezentuje zbiór ${\ displaystyle | A | ^ {k}}$ ciągi znaków (słowa z parametrem 0), uzyskane przez zastąpienie $każdego$ symbolu wieloznacznego Ten zestaw ciągów nazywany jest $zestawem$ kostki kombinatorycznej , a jego wymiarem. Jednowymiarowy sześcian kombinatoryczny można nazwać linią kombinatoryczną .

W kostce kombinatorycznej każda kopia określonego znaku wieloznacznego musi mieć ten sam zamiennik. Uogólnienie słów parametrycznych umożliwia zastąpienie różnych kopii tego samego symbolu wieloznacznego różnymi znakami z alfabetu w kontrolowany sposób. Jeśli $alfabetem$ i jest $}$ z działaniem na , to słowo parametru oznaczone etykietą jest $k}$$ZA$$\ displaystyle$ A $}$ -słowo parametru wraz z przypisaniem elementu grupy do każdego symbolu wieloznacznego w słowie. Pierwszemu wystąpieniu każdego symbolu wieloznacznego należy przypisać element tożsamości grupy. $symbolu$ ciągi reprezentowane przez słowo parametru z etykietą są uzyskiwane przez wybranie znaku dla każdego wieloznacznego i zastąpienie wyniku połączenia tego znaku elementem grupy oznaczającym każdą kopię tego znaku. Zestaw wszystkich $\$ -oznaczonych displaystyle $k}$ słowa nad , o długości ${\ displaystyle$$n}$ są oznaczone $n} {k}}}$ .

Przykład

W grze w kółko i krzyżyk komórkom planszy można nadać dwie współrzędne całkowite $Displaystyle \$ alfabetu $\$ . Połączenie tych dwóch współrzędnych daje łańcuch reprezentujący każdą komórkę, jeden z dziewięciu ciągów ${\ Displaystyle 11,12,13,21,22,23,31,32}$ lub ${\ Displaystyle 33}$ . W tym alfabecie jest siedem jednoparametrowych słów o długości dwóch, słowa ${\ Displaystyle 1 *, 2 *, 3 *, * 1, * 2, * 3,}$ i ${\ Displaystyle **}$ . Odpowiednie linie kombinatoryczne tworzą siedem z ośmiu linii trzech komórek w rzędzie planszy w kółko i krzyżyk; $kombinatorycznej$$słowo$ jednoparametrowe odpowiada _ ${\ Displaystyle **}$ odpowiada linii kombinatorycznej ${\ Displaystyle \ {11,22,33 \}}$ .

Jednak w tym zestawie linii kombinatorycznych brakuje jednej z ośmiu zwycięskich linii gry w kółko i krzyżyk: linii antydiagonalnej. { $\ {13,22,31 \}}$ Displaystyle 13 Możliwe jest otrzymanie tej linii jako linii kombinatorycznej (bez uwzględnienia jakichkolwiek innych kombinacji komórek, które byłyby nieważne dla kółko i krzyżyk) za pomocą grupy z dwoma elementami i akcji, w której element nietożsamościowy zamienia litery alfabetu ${\ Displaystyle 1}$ i ${\ Displaystyle 3}$$miejscu$ element na . Istnieje osiem oznaczonych jednoparametrowych słów o długości dwóch dla tej akcji, z których siedem uzyskuje się z nieoznakowanych słów jednoparametrowych przy użyciu etykiety tożsamości dla wszystkich symboli wieloznacznych. Te siedem ma te same linie kombinatoryczne, co poprzednio. Ósme słowo z etykietą składa się ze słowa $oznaczonego$$elementem$ tożsamości dla pierwszego i odwrotnym elementem braku tożsamości dla drugiego $*}$ ; do $jego kombinatoryczna$ jest ostatnią wygrywającą linią planszy

Kompozycja

$($$m$ parametrów całkowitych jest połączenie dwóch słów parametrów, $\ Displaystyle f \ w A {\ tbinom$ sol ${k}}}$ , aby utworzyć inne słowo parametru ${\ Displaystyle f \ circ g \ w A {\ tbinom {n} {k}}}$ . Aby to zrobić, po prostu zastąp każdą kopię symbolu wieloznacznego w th $i$ znak i $}$$\$$w$ . To z konieczności stworzy słowo o długości $które$$przynajmniej$ raz użyje każdego z symboli wieloznacznych w kolejności rosnącej, więc tworzy prawidłowy $}$ parametr słowo długości ${\ displaystyle n}$ . To pojęcie kompozycji można również rozszerzyć na komponowanie etykietowanych słów parametrów (zarówno przy użyciu tego samego alfabetu, jak i akcji grupowej), poprzez zastosowanie akcji grupowej do znaków zastępowanych innymi niż symbole wieloznaczne i tworzenie etykiet grupowych dla zastępowanych znaków wieloznacznych. Podzbiór kostki kombinatorycznej jest mniejszym sześcianem kombinatorycznym, jeśli można go uzyskać za pomocą kompozycji w ten sposób.

Wyliczanie kombinatoryczne

Liczba słów parametrów w $}$$A {\ tbinom {n} {k$ rozmiarze to liczba Stirlinga za $Displaystyle$ } drugi rodzaj ${\ Displaystyle \ textstyle \ lewo \ {{r + n \ na szczycie r + k} \ prawo \} _ {r}}$ . Liczby te zliczają liczbę podziałów liczb całkowitych z zakresu $}$$]$ w niepuste podzbiory, tak że pierwsze $liczby$ należą do różnych podzbiorów ${\ displaystyle [ r+1,n+r]}$ typu można umieścić w bijektywnej równoważności ze słowami parametru, tworząc słowo ze znakiem dla każdej z $liczb$ całkowitych z zakresu , ustawiając tę ​​wartość znaku na liczbę całkowitą należącą do tego $samego$ podzbioru partycji lub znak wieloznaczny dla każdego podzbioru partycji, w ${\ Displaystyle [1, r]}$ . Liczby $Stirlinga$ są zgodne z prostą relacją powtarzalności dzięki której można je łatwo obliczyć.

Aplikacje

W teorii Ramseya słowa parametryczne i kostki kombinatoryczne mogą być użyte do sformułowania twierdzenia Grahama-Rothschilda , zgodnie z którym dla każdego skończonego alfabetu i akcji grupowej oraz dla każdej kombinacji wartości całkowitych ${\ displaystyle m}$ , ${\ displaystyle k }$ i istnieje wystarczająco duża liczba $taka$ na $-wymiarowy$ że ​​jeśli każdy $sześcian$ ciągach o ${\ displaystyle n}$$ma$ przypisany jeden z $kolorów$ sześcian $wtedy$ -wymiarowe dwuwymiarowy , którego wszystkie podsześciany mają ten sam kolor. Wynik $ten$ jest kluczową podstawą strukturalnej teorii Ramseya służy do zdefiniowania liczby Grahama , ogromnej liczby używanej do oszacowania wartości dla określonej kombinacji wartości.

W informatyce , w problemie wyszukiwania zduplikowanego kodu , kod źródłowy dla danej procedury lub modułu może zostać przekształcony w słowo parametru poprzez przekształcenie go w sekwencję tokenów oraz dla każdej nazwy zmiennej lub podprogramu, zastępując każdą kopię tej samej nazwy tym samym symbolem wieloznacznym. Jeśli kod zostanie zduplikowany, wynikowe słowa parametrów pozostaną takie same, nawet jeśli zmieniono nazwy niektórych zmiennych lub podprogramów. Bardziej wyrafinowane algorytmy wyszukiwania mogą znaleźć długie zduplikowane sekcje kodu, które tworzą podciągi większych repozytoriów kodu źródłowego, umożliwiając wzajemne zastępowanie znaków wieloznacznych.

Ważnym szczególnym przypadkiem słów parametrycznych, dobrze zbadanych w kombinatoryce słów, są słowa częściowe . Są to łańcuchy ze znakami wieloznacznymi, które mogą być zastępowane niezależnie od siebie, bez wymogu, aby niektóre z zastępowanych znaków były równe lub kontrolowane przez akcję grupową. W języku słów parametrycznych słowo częściowe można opisać jako słowo parametryczne, w którym każdy symbol wieloznaczny pojawia się dokładnie raz. Jednakże, ponieważ nie ma powtórzeń symboli wieloznacznych, częściowe słowa można zapisać prościej, pomijając indeksy dolne symboli wieloznacznych.

Zobacz też

• Wyrażenie regularne