Defect theorem and its generalizations

"Jeśli zbiór X nie jest kodem, to istnieje zbiór Y taki, że |Y | < |X| oraz każdy element należący do zbioru X^∗ posiada jednoznaczną faktoryzację na elementy ze zbioru Y" - tak w ogólności brzmi twierdzenie o efekcie, które może zostać dostosowane do różnych koncepcji kodów. W pracy zostały zawarte zagadnienia dotyczące kodów zmiennej długości, kodów relacyjnych i kodów klockowych w kontekście wspomnianego twierdzenia o defekcie. Obok podstawowych definicji i twierdzeń, praca zawiera szereg przykładów, algorytmów i pseudokodów pozwalających teoretyczne koncepcje zrealizować w praktyce. Opisane algorytmy zostały zaimplementowane w programie CodeFinder będącym integralną częścią niniejszej pracy. W pracy można również znaleźć zagadnienia z innych dziedzin, które są powiązane z omawianymi problemami. Praca zawiera wiadomości dotyczące między innymi: układów równań na słowach, teorii grafów, czy teorii języków i automatów.

"If the set X is not a code, then there exists a set Y such that |Y | < |X|, and each element belonging to X^* has a unique factorization over the elements of Y" - that in general is the defect theorem, which can be adapted to different concepts of codes. This thesis covers issues concerning variable-length codes, relational codes and brick codes in the context of defect theorem. Besides the basic definitions and theorems, the thesis contains a number of examples, algorithms and pseudo-code allowing to implement those theoretical concepts in practice. These algorithms were implemented in the program CodeFinder which is an integral part of this work. In this thesis you can also find information on other fields, that are related to the problems mentioned. Among other you can find issues related to: systems of equations on words, graph theory or the theory of languages and automata.