złożoność półjęzyka

Dla dowolnego języka ponad zdefiniuj Słowami, składa się ze wszystkich dla których istnieje o równej długości, tak że . $L$ $\Sigma^*$

L_{1 / 2} = {x \in Σ^{*} : x y \in L, y \in Σ^{| x |}} .

$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$

L_{1 / 2}

$L_{1/2}$

x

$x$

y

$y$

x y \in L

$xy\in L$

Ćwiczenie w książce Sipsera ma na celu wykazanie, że jest regularne, gdy jest. Widziałem dwa odrębne rozwiązania, i oba pociągają za sobą gwałtowny wzrost stanów. $L_{1/2}$ $L$

Pytanie: czy ktokolwiek może skonstruować rodzinę języków taki sposób, że automat kanoniczny dla jest znacznie (powiedzmy, wykładniczo) większy niż dla ? Moje dotychczasowe starania zwiększają tylko rozmiar państwa o ! $\{L_n\}$ $(L_n)_{1/2}$ $L$ $+1$

fl.formal-languages automata-theory

— Aryeh
źródło

nie wspominasz o częściowo oczywistym problemie minimalizacji DFA. nie widziałem dowodów, ale może nie biorą ich pod uwagę. a minimalizacja DFA po uruchomieniu na sprawdzonej konstrukcji może znacznie uprościć DFA ...?

— vzn

Konstrukcje w dowodach są abstrakcyjne i wcale nie jest jasne, jak je zminimalizować za pomocą standardowych technik.

— Aryeh

Czy możesz opublikować najlepszą rodzinę języków, którą znalazłeś?

— Diego de Estrada

nie jest to wymagane, aby odpowiedzieć na twoje Q, ale może być pomocne naszkicowanie konstrukcji. inną opcją jest empiryczne zaatakowanie problemu losowymi modułami FSM

— od

Zobacz artykuł Mike'a Domaratzkiego, Złożoność państwowa proporcjonalnych przeprowadzek

http://dl.acm.org/citation.cfm?id=782471

http://www.cs.umanitoba.ca/~mdomarat/pubs/sc_jalc.ps

— Jeffrey Shallit
źródło

Doskonały! twierdzenie 6 daje rodzinę języków z a twierdzenie 3 podaje górną granicę , więc jest mało miejsca na ulepszenia.

Ω (e^{\sqrt{n \log n}})

$\Omega(e^{\sqrt{n\log n}})$

O (n e^{\sqrt{n \log n}})

$O(n e^{\sqrt{n\log n}})$

— Diego de Estrada