Separowalność słów przez automaty skończone

W pracy zebrano dotychczasowe wyniki dotyczące problemu separowalności słów. Zaprezentowano najnowsze oszacowanie rzędu n^{1/3} log^k n, udowodnione przez Z. Chase w 2022 r. Przedstawiono analogię dowodu do argumentu zawartego w pracy J. M. Robsona z 1989 r., który prowadzi do oszacowania rzędu n^{1/2} log^k n. Rozważono problem separowalności słów przez automaty permutacyjne i przedstawiono uproszczenie dowodu zawartego w pracy J. M. Robsona z 1996 r., prowadzące do słabszego jedynie o czynnik logarytmiczny niż w źródle oszacowania górnego rzędu n^{1/2} log^k n. Przedstawiono również uogólnienie problemu – problem separowalności języków. Wskazano błąd w dowodzie odnalezionym w artykule G. Zetzsche, dotyczącym NP-zupełności problemu separowalności języków regularnych przez automaty deterministyczne. Przedstawiono też poprawny dowód tego faktu. Udowodniono, że problem separowalności języków regularnych przez automat permutacyjny jest NP-zupełny.

The thesis compiles existing results related to the word separability problem. The latest upper bound of order n^{1/3} log^k n, proven by Z. Chase in 2022, is presented. An analogous proof from J. M. Robson's work from 1989, which leads to an estimation of order n^{1/2} log^k n, is provided as well. The problem of word separability by permutation automata is explored, and a simplification of the proof from J. M. Robson's 1996 work is presented, resulting in upper bound of order n^{1/2} log^k n which is weaker only by a logarithmic factor compared to the original estimate. An extension of the problem is introduced, considering the separability problem for languages. An error, identified in G. Zetzsche's article on the NP-completeness of the separability problem for regular languages by deterministic automata, is pointed out. A corrected proof for this fact is also presented. Furthermore, it is proven that the separability problem for regular languages by permutation automata is NP-complete.