Ile słów długości


9

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 llisty. Każde słowo ma dokładnie długośćk. Umowa jest, jeśliajb jest na liście, gdzie jest zatem symbolem wieloznacznym / nieważnym ajbnigdy więcej nie pojawi się na liście. (To samo dotyczy, jeślia=b, albo jeśli j=0 i stąd zabronione jest podtytuł ab.)

Przykład gdzie k=4 i l=5:

abcd
bdce
dcba <- zabronione, ponieważ dc pojawił się w linii powyżej
aeed <- zabronione, ponieważ ad 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 ajb w alfabecie l litery, ile słów długości k 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.


(1) Nie rozumiem zgodności między twoim pierwszym pytaniem a przytoczonym wcześniej przykładem. Jakie są dane z twojego przykładu? (2) Czy w pierwszym pytaniu używasz k do dwóch różnych celów?
Tsuyoshi Ito

Odnośnie (2), tak, popełniłem błąd, teraz edytowany, dziękuję.
Aaron Sterling

Odnośnie (1) chciałbym wiedzieć „ile miejsca mi zostało”, gdy pojawi się częściowe słowo. Ale tak, prawdziwe pytanie brzmi: jak tworzyć listy takie jak ta, która pojawia się w przykładzie (bez zabronionych częściowych słów). Zatem dane wejściowe byłyby wartościamik i loraz pożądaną liczbę słów do wygenerowania na liście, z których wszystkie miały „unikanie wcześniejszej właściwości częściowych słów”.
Aaron Sterling

2
@Aaron, nie wiem, jaka jest twoja ostateczna aplikacja, ale sekwencje Davenporta-Schinzela (i uogólnienia) pytają o maksymalną długość łańcucha, który nie zawiera określonego powtarzającego się wzorca. To powiązane pojęcie.
Suresh Venkat

1
Seth Pettie badał również bardzo sprytne uogólnienia dotyczące zakazanych podmorskich dzieł.
Suresh Venkat

Odpowiedzi:


4

Oto szczególny przypadek: liczba dwójkowych słów długości k tak, że nie pojawiają się dwa kolejne F(k+3), gdzie F(n) jest nth Liczba Fibonacciego (od F(1)=1,F(2)=1). Dowodem jest reprezentacja Zeckendorfa .

EDYCJA: Możemy rozszerzyć tę początkową specjalną skrzynkę na nieco większy specjalny przypadek a0a. Rozważ ciągi długościk ponad alfabet wielkości l+1 tak, że list anie pojawia się dwa razy pod rząd. Pozwolićf(k)być liczbą takich ciągów (które nazywamy „prawidłowymi”). Twierdzimy, że:

f(k)=lf(k1)+lf(k2)
f(0)=1,f(1)=l+1
Intuicja polega na tym, że możemy skonstruować prawidłowy ciąg długości k przez: a) przyleganie do dowolnego z l litery, które nie są a na prawidłowy ciąg długości k1lub b) przylegające do litery a a następnie każdy inny list oprócz a na prawidłowy ciąg długości k2.

Możesz sprawdzić, czy poniższy formularz jest zamknięty dla powyższej rekurencji: gdzie rozumiemy gdy .

f(k)=i=0k(k+1ii)lki
(ni)=0i>n

EDYCJA 2: Wyrzućmy jeszcze jedną sprawę - a . łańcuchy nad alfabetem elementowym, który nie zawiera podłańcucha , „ważny”, a oznacza zbiór prawidłowych łańcuchów o długości . Ponadto, zdefiniujmy jako podzbiór składający się z łańcuchów zaczynających się na a na te, które nie zaczynają się na . Na koniec niech,,.0b,ablabSkkTkSkbUkbf(k)=|Sk|g(k)=|Tk|h(k)=|Uk|

Obserwujemy i . Następnie wnioskujemy o następujących nawrotach: Pierwszy wynika z faktu, że dodanie na początku dowolnego elementu daje element . Drugi wynika z obserwacji, że możemy zbudować element , dodając dowolny znak oprócz z przodu dowolnego elementu lub dodając dowolny znak oprócz lub z przodu dowolnego elementu w .g(0)=0,h(0)=1,f(0)=1g(1)=1,h(1)=l1,f(1)=l

g(k+1)=f(k)h(k+1)=(l1)h(k)+(l2)g(k)
bSkTk+1Uk+1bUkabTk

Następnie przestawiamy równania rekurencyjne, aby uzyskać:

f(k+1)=g(k+1)+h(k+1)=f(k)+(l1)h(k)+(l2)g(k)=f(k)+(l1)f(k)g(k)=lf(k)f(k1)

Możemy uzyskać raczej nieprzejrzyste zamknięte rozwiązanie tego nawrotu, trochę się mijając z generowaniem funkcji lub, jeśli jesteśmy leniwi, kierujemy się prosto do Wolfram Alpha . Jednak przy odrobinie googlingu i przeszukiwania w OEIS , okazuje się, że faktycznie mamy: gdzie jest wielomianem drugiego rodzaju (!) .

f(k)=Uk(l/2)
Ukkth

To bardzo interesujące, dziękuję.
Aaron Sterling

2

Zupełnie inne podejście do pierwszego pytania ponownie wykorzystuje odpowiedzi na ostatnie pytanie dotyczące generowania słów w zwykłym języku : wystarczy zastosować te algorytmy dla długości w zwykłym języku gdzie jest alfabetem.kΣaΣjbΣΣ


Dzięki. Zastanawiałem się, czy może istnieć związek, a twoja odpowiedź tutaj dała mi impuls, aby spojrzeć na wspomniane tam dokumenty, a jeden z nich zdecydowanie rozwiązuje jeden z problemów, które rozważam.
Aaron Sterling

0

Zaktualizowano: ta odpowiedź jest niepoprawna :

przy założeniu, jest stała, można policzyć liczbę sposobów, wzór można dopasować: pierwszy symbol może być dopasowana w pewnej pozycji , i mają możliwości wcześniejszy, między a i dla pozostałej części łańcucha, przez co w sumie . Jak zauważył Tsuyoshi Ito w komentarzach, liczba ta nie jest liczbą różnych słów pasującychjajba1ikj1li1ljablkji1

i=1kj1li1ljlkji1=(kj1)lk2
ajbponieważ jedno słowo może pasować do tego samego wzoru na różne sposoby. Na przykład, jest dopasowywana trzy razy w , dwa razy w , a dwa razy w . Możemy spróbować policzyć liczbę sposobów dopasowania wzorców kilka razy i wyświetlić wyrażenie „wykluczenie włączenia”, ale sposoby, w jakie wzór może się nakładać, powodują, że jest to zbyt długie.aaaaaaababababaabb

W przypadku pierwszego pytania, przy założeniu, że nie jest ustalone, tzn. Że chcemy uniknąć osadzania słowa :jab

  • albo pierwszy symbol nigdy nie pojawia się, co stanowi możliwych słówa(l1)k
  • lub pojawia się najpierw w jakiejś pozycji , a następnie nie możemy użyć w pozostałej części słowa: istnieją opcje dla współczynnika do , i wyborów dla reszty, dając w sumie możliwe słowa. Czy jest nieistotne.a1ikb(l1)i1a(l1)kii=1k(l1)i1(l1)ki=k(l1)k1a=b

W przypadku drugiego pytania nie mam wiele do zaproponowania; istnieje związek z osadzaniem słów, ale wyniki, które znam o złych sekwencjach dla Lemmy Higmana, nie mają natychmiastowego zastosowania.


Dziękuję bardzo, Sylvain, choć nie sądzę, żeby to było w porządku. Możemy użyć później w słowie, jeśli pojawi się . Po prostu nie można użyć jeśli istnieją dokładnie litery między i , jeśli pojawił wcześniej. Być może jednak nie rozumiem twojego argumentu. babjabajb
Aaron Sterling

Przepraszam, nie byłem pewien, czy został naprawiony, czy nie. Zredagowałem odpowiedź również za pomocą poprawionego . jj
Sylvain,

1
Nie sądzę, aby przypadek fixed-j był poprawny. Na przykład, jeśli k = 4 i j = 1, słowo aabb jest odejmowane dwukrotnie. Nie przeczytałem przypadku nie-naprawionego-j.
Tsuyoshi Ito,

@Tsuyoshi Ito: masz rację, w tym przypadku nie ma unikalnego dopasowania.
Sylvain,

Proszę zaznaczyć niepoprawną odpowiedź jako taką.
Tsuyoshi Ito,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.