EDYTOWANO, ABY DODAĆ : Na to pytanie zasadniczo udzielono odpowiedzi; zobacz ten wpis na blogu, aby uzyskać więcej informacji. Dziękujemy wszystkim, którzy opublikowali tutaj komentarze i odpowiedzi.
PYTANIE ORYGINALNE
Jest to, mam nadzieję, mądrzejsza i lepiej poinformowana wersja pytania, które zadałem na MathOverflow. Kiedy zadałem to pytanie, nie znałem nawet nazwy dziedziny matematyki, w której tkwi mój problem. Teraz jestem całkiem pewien, że leży ona w kombinatoryce algorytmicznej na słowach częściowych. (Najnowsza książka na ten temat tutaj .)
Chcę zrobić listę słów listy. Każde słowo ma dokładnie długość. Umowa jest, jeśli jest na liście, gdzie jest zatem symbolem wieloznacznym / nieważnym nigdy więcej nie pojawi się na liście. (To samo dotyczy, jeśli, albo jeśli i stąd zabronione jest podtytuł .)
Przykład gdzie i :
<- zabronione, ponieważ pojawił się w linii powyżej
<- zabronione, ponieważ pojawił się w pierwszej linii
Znaleziona przeze mnie literatura na temat „częściowych słów, których można uniknąć”, jest nieskończona - ostatecznie nie można uniknąć jakiegoś wzoru słów, jeśli rozmiar słowa jest wystarczająco duży. Chciałbym znaleźć skończone wersje takich twierdzeń. Pytanie:
Biorąc pod uwagę częściowe słowo formy w alfabecie litery, ile słów długości unikaj go i czy można je jawnie wytworzyć w czasie wielomianowym?
Nie oczekuję, że powyższe pytanie będzie trudne i, chyba że brakuje mi subtelności, sam bym mógł ją obliczyć. Prawdziwym powodem, dla którego publikuję na tej stronie jest to, że muszę dowiedzieć się znacznie więcej o właściwościach takich list słów dla mojej aplikacji, dlatego mam nadzieję, że ktoś odpowie na kolejne pytanie:
Czy zbadano to ogólnie? Co rozważają niektóre dokumenty, nie tylko to, czy częściowe słowo jest w końcu nieuniknione, ale „ile czasu” zajmuje, zanim staje się nieuniknione?
Dzięki.