상태 복잡성

상태 복잡성은 다양한 종류의 유한 오토마타와 같은 추상 오토마타의 크기를 다루는 이론 컴퓨터 과학의 영역입니다.이 영역의 고전적인 결과는 결정론적 유한 오토마톤에 의해 n $(\displaystyle$ n $)$ 상태 $n$ 비결정론적 유한 오토마톤을 $n$ 하는 데 최악의 경우 $2^{n}$ 2n $(\$ })의 상태가 필요하다는 것이다.

유한 오토마타의 변형 간 변환

유한 오토마타는 결정론적이고 비결정론적인 단방향(2DFA, NFA) 및 양방향(2DFA, 2NFA)일 수 있습니다.다른 관련 클래스에는 Unmarkous(UFA), Self-Verifying(SVFA), Alternating(AFA) 유한 오토마타가 있습니다.이러한 오토마타는 쌍방향(2UFA, 2SVFA, 2AFA)도 가능합니다.

이 모든 기계들은 정확히 정규 언어를 받아들일 수 있다.그러나 동일한 언어(상태의 수로 측정)를 수용하기 위해 필요한 다른 유형의 오토마타의 크기는 다를 수 있다.두 가지 유형의 유한 오토마타에 대해 이들 사이의 상태 복잡도 트레이드오프는 정수 $함수$ f ${displaystyle$ f $}$ 입니다 $f$ . $f(n)$ 서 f $n)$ { $displaystyle f(n$ )}는 $f(n)$ 첫 번째 ${displaystyle$ n $}$ 상태 $n$ 오토마타에 의해 인식되는 모든 언어를 인식할 수 있는 두 번째 유형의 오토마타에서 최소 상태 수 있습니다.type. 다음 결과가 알려져 있습니다.

NFA에서 DFA: $(\$ 2 $^{n})$ 상태 $2^{n}$ .이것은 Labin과 ^[1]Scott의 서브셋 구성이며, Lupanov에 의해 ^[2]최적이란 것이 증명되었습니다.

UFA에서 DFA: $($ 2 $^{n})$ 의 $2^{n}$ 주, 슈미트에 의한^[4] 초기 하한선은 더 작았다.^[3]
NFA에서 UFA: $(\displaystyle$ 2 $^{n}-1)$ 상태 $2^{n}-1$ , ^[3]렁 참조.슈미트에 ^[4]의해 더 작은 하한선이 있었다.
SVFA에서 DFA: $\Theta (3^{n/3})$ ( 3 $\Theta (3^{n/3})$ / $\Theta (3^{n/3})$ ) { $displaystyle$ \ $Theta$ ( 3 $^$ ${n$ / $3$ ) }개 $\Theta (3^{n/3})$ 상태, '지라스코바' 및 '피기즈니^[5]' 참조
2DFA에서 DFA: $n(n^{n}-(n-1)^{n})$ ( $n(n^{n}-(n-1)^{n})$ - ( $n(n^{n}-(n-1)^{n})$ - $n(n^{n}-(n-1)^{n})$ ) $n(n^{n}-(n-1)^{n})$ { $displaystyle$ n ( n $n(n^{n}-(n-1)^{n})$ ^ { $n$ } - ( n - 1 )^{ $n}$ } 상태 $n(n^{n}-(n-1)^{n})$ , "Kapoutsis"^[6] 참조.Shepherdson에^[7] 의한 초기 건설은 더 많은 주를 사용했고, Moore에 의한^[8] 초기 하한선은 더 작았다.
2DFA에서 NFA ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$ ( ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$ + ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$ ) ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$ ( $)$ ({ $style {binom {2n}{n+1$ }) = ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$ O $({\frac {4^{n}}}{\fracrc$ { $4^{$ n ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$ (Kapoutsis ^[6]참조)Birget에 의한^[9] 초기 건설은 더 많은 주를 사용했다.
2NFA에서 NFA ${\binom {2n}{n+1}}$ ( ${\binom {2n}{n+1}}$ ) ${\binom {2n}{n+1}}$ { $displaystyle {binom {2n}{n+1$ "Kapoutsis"^[6] 참조.
- 2NFA에서 NFA로 $)$ { $displaystyle$ O(4 $^{n})$ 상태 $O(4^{n})$ , ^[10]Vardi를 참조하십시오.
AFA에서 DFA: $2^{2^{n}}$ $({$ 2 $^{2^{n}})$ 상태 $2^{2^{n}}$ , Chandra, Kozen 및 Stockmeyer ^[11]참조.
AFA에서 NFA: $($ 2 $^{n})$ 의 $2^{n}$ 주(펠라, 위르겐센, 유 참조).^[12]
2AFA에서 DFA: $({$ 2^{ $n2^{n$ (라드너, 립톤 및 스톡마이어 ^[13]참조).
2AFA에서 NFA: $2^{\Theta (n\log n)}$ ( $2^{\Theta (n\log n)}$ log $2^{\Theta (n\log n)}$ $){$ $displaystyle$ 2 $^{$ \ $Theta (n\log$ n $2^{\Theta (n\log n)}$ Geffert 및 Okhotin을 ^[14]참조하십시오.

2DFA 대 2NFA 문제와 로그 공간

컴퓨터 과학에서 해결되지 않은 문제:

$모든$ $n개(displaystyle$ n $)$ 상태 $n$ 2NFA에는 $\operatorname {poly} (n)$ 한 폴리 $\operatorname {poly} (n)$ δ( $)$ { $displaystyle \operatorname {poly}(n)}$ 상태 $\operatorname {poly} (n)$ 2DFA가 있습니까?

(컴퓨터 사이언스의 미해결 문제 증가)

모든 2NFA를 다항식 $p(n)$ 의 2DFA로 변환할 수 있는지, 즉 $n개$ $\displaystyle$ n개 $n$ \ $state$ 2NFA마다 p $(n)\$ $displaystyle$ p $(n)-$ 2DFA가 $p(n)$ 존재하는지 여부는 미해결 문제이다.이 문제는 계산 복잡도 이론의 P ^[15]대 NP 문제와 비교한 Sakoda와 Sipser에 의해 제기되었다.Berman과^[16] Lingas는 이 문제와 L 대 L 사이의 공식적인 관계를 발견했습니다.NL 미해결 문제이 관계는 Kapoutsis에 ^[17]의해 더욱 상세해졌다.

유한 오토마타에 대한 운영의 복잡성 상태

언어 ${\({displaystyle\circ})$ 및 $\circ$ 자동 X(DFA, NFA 등) 패밀리의 바이너리 규칙성 유지 연산에서 $),({$ $displaystyle\circ$ $})$ 의 $\circ$ 상태 복잡도는 다음과 같은 정수 $f(m,n)$ f $m,$ n $)$ 이다 $f(m,n)$ .

각 m-상태 X-automaton A 및 n-상태 X-automaton B에 $L(A)\circ L(B)$ $A$ ) $L(A)\circ L(B)$ L $)$ \ $displaystyle L$ $($ A $)$ \ $circ L$ $(B$ $)$ $f(m,n)$ 、 $f(m,n)$
모든 정수 m, n에는 m-상태 X-automaton A와 n-상태 X-automaton B가 존재하며 $L(A)\circ L(B)$ L ( $A)$ L $L(A)\circ L(B)$ ( B $L(A)\circ L(B)$ ) \ $displaystyle$ L ( $B$ ) \ $circ$ L ( B )는 $L(A)\circ L(B)$ 적어도 $f(m,n)$ f ( $f(m,n)$ , $f(m,n)$ $){$ $displaystyle$ f ( $m$ , n )의 $f(m,n)$ $L(A)\circ L(B)$ 를 가져야 합니다.

인수의 수에 관계없이 동일한 정의가 적용됩니다.

DFA 운영의 국가 복잡성에 대한 첫 번째 결과는 Maslov와 Yu, Zhuang 및 Salomaa에 의해 발표되었다.^[19] Holzer와 Kutrib은 NFA에서 운영의 복잡성을 개척했습니다.기본 조작에 대해 알려진 결과는 다음과 같습니다.

유니언

$L_{1}$ $({$ 에는 $L_{1}$ m개의 상태가 필요하고 언어 $({$ $L_{$ $2})$ 에는 $L_{2}$ n개의 상태가 필요한 경우 $L_{1}\cup L_{2}$ † $({$ 1}\ $cup L_2})에는$ 몇 개의 $L_{1}\cup L_{2}$ 상태가 $L_{1}\cup L_{2}$ 합니까?

DFA: $mn$ \ $displaystyle$ mn $,$ Maslov와 Yu, Zhuang과 Salomaa ^[19]참조^[18].
NFA: $m+n+1$ + $m+n+1$ + $({style$ m $+n+1$ } 상태 $m+n+1$ , Holzer 및 Kutrib ^[20]참조).
UFA: $mn+m+n$ + m $mn+m+n$ + $mn+m+n$ \ $m+nm2^{0.79m}$ $displaystyle$ $m+nm2^{0.79m}$ + $m$ + $m+nm2^{0.79m}$ $mn+m+n$ $m+nm2^{0.79m}$ 0. $m+nm2^{0.79m}$ m \ $displaystyle$ m + $nm$ 2 ^ { $0$ . $79$ m $m+nm2^{0.79m}$ } $m+nm2^{0.79m}$ 는 $m+nm2^{0.79m}$ , 「지라섹」, 「지라스코바」, 「셰베즈」^[21]를 참조해 주세요.
$지라섹$ , 지라스코바 $,$ ^[22] 사바리를 참조해 $mn$ $주세요.$
2DFA: m $m+n$ + $m+n$ ({ $displaystyle$ m + $n$ } ~ $4m+n+4$ m + $4m+n+4$ + $4m+n+4$ ({ $displaystyle 4$ m + $n$ + $4$ }) $m+n$ 에서 $4m+n+4$ Kunc와 Okhotin을 ^[23]참조해 주세요.
2NFA: $m+n$ + $m+n$ \ $style$ m + n \ style $m+n$ m + $n$ , 、「 Kunc and Okhotin ^[24]」를 참조해 주세요.

교차로

$L_{1}\cap L_{2}$ $L_{1}\cap L_{2}$ $(\$ L_ ${2})$ 에는 $L_{1}\cap L_{2}$ 몇 개의 상태가 필요합니까?

DFA: $mn$ \ $displaystyle$ mn $,$ Maslov와 Yu, Zhuang과 Salomaa ^[19]참조^[18].
NFA: $\displaystyle$ mn $.$ Holzer와 ^[20]Kutrib을 참조하십시오.
$:$ $지라세크$ , 지라스코바 및 ^[21]셰베즈를 참조해 $주십시오$ .
$지라섹$ , 지라스코바 $,$ ^[22] 사바리를 참조해 $mn$ $주세요.$
2DFA: $m+n$ m + $m+n$ ({ $displaystyle$ m $+n$ ~ $m+n+1$ m + $m+n+1$ + $({displaystyle$ m $+n+1})$ 상태 $m+n+1$ $m+n+1$ 에서 Kunc 및 Okhotin을 ^[23]참조하십시오.
2NFA: $m+n$ m + $m+n$ ({ $displaystyle$ m $+n$ ~ $m+n+1$ + $m+n+1$ + $({displaystyle$ m $+n+1})$ 상태 $m+n+1$ $m+n$ 에서 Kunc 및 Okhotin을 ^[24]참조하십시오.

보완

언어 L이 n개의 상태를 필요로 하는 경우, 그 보완은 몇 개의 상태를 필요로 합니까?

$승인$ 상태와 거부 상태를 교환하여n개의 $n$ $상태$ 를 표시합니다 $.$
$2^{n}$ { $displaystyle$ 2 $^{n}}$ 개 $2^{n}$ 주(Birget ^[25]참조).
UFA: $n^{{\tilde {\Omega }}(\log n)}$ n $n^{{\tilde {\Omega }}(\log n)}$ ~ ( $n^{{\tilde {\Omega }}(\log n)}$ n $n^{{\tilde {\Omega }}(\log n)}$ ){\ $displaystyle$ n $^{\tilde$ {\Omega }}( $log$ n)}}}} 상태 $n^{{\tilde {\Omega }}(\log n)}$ ${\sqrt {n+1}}\cdot 2^{0.5n}$ . Gös, Kiefer 및 ^[26]Yuan을 참조하고, ${\sqrt {n+1}}\cdot 2^{0.5n}$ n + ${\sqrt {n+1}}\cdot 2^{0.5n}$ † ${\sqrt {n+1}}\cdot 2^{0.5n}$ 0.5 ${\sqrt {n+1}}\cdot 2^{0.5n}$ 2 $^{0$ .5}}} khev 상태 참조.
$수락$ 상태와 거부 상태를 교환하여n개의 $n$ $상태$ 를 표시합니다 $.$
2DFA: $n개$ 주에서 $4n$ $4개$ 주 $(Geffert$ , Meregetti 및 Pighzzini ^[28]참조 $n$ $4n$ ).

연결

$L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ $=$ { $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ 1 $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ W $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ 1 $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ W 2 $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ 2 $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ { $displaystyle L_{1} l_{2}$ =\{ $w_{1$ }\ $mid$ w_{ $1}\in$ L_2 $}}}$ 은 $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ 몇 개의 $상태$ 가 필요합니까?

DFA: $m\cdot 2^{n}-2^{n-1}$ $m\cdot 2^{n}-2^{n-1}$ - $m\cdot 2^{n}-2^{n-1}$ $m\cdot 2^{n}-2^{n-1}$ ({ $displaystyle$ m\ $cdot$ 2^{ $n}-2^{n-1})$ 상태 $m\cdot 2^{n}-2^{n-1}$ , "Maslov와 Yu, Zhang과 Saloma"^[19] 참조.
$m+n$ + $(style$ m $+n)$ 상태 $m+n$ , Holzer 및 Kutrib ^[20]참조.
UFA: ${\frac {3}{4}}2^{m+n}-1$ 4 ${\frac {3}{4}}2^{m+n}-1$ m + ${\frac {3}{4}}2^{m+n}-1$ - ${\frac {3}{4}}2^{m+n}-1$ ({ $displaystyle$ { $frac$ { $3$ } { $4$ } $2$ ^ { $m$ + n } - $1$ )주 ${\frac {3}{4}}2^{m+n}-1$ (지라섹, 지라스코바 및 셰베즈 ^[21]참조).
SVFA: $\Theta (3^{n/3}2^{m})$ ( $\Theta (3^{n/3}2^{m})$ $\Theta (3^{n/3}2^{m})$ / $\Theta (3^{n/3}2^{m})$ 3 2 $\Theta (3^{n/3}2^{m})$ $){$ $displaystyle$ \ $Theta$ ( $3 ^$ { n / $3$ } 2 ^ { $m$ } }개 $\Theta (3^{n/3}2^{m})$ 상태, "지라섹", "지라스코바"^[22] 및 "사바리" 참조.
2DFA: ${\frac {2^{\Omega (n)}}{\log m}}$ ${\frac {2^{\Omega (n)}}{\log m}}$ ${\frac {2^{\Omega (n)}}{\log m}}$ m ${\$ {\ $log$ m $2m^{m+1}\cdot 2^{n^{n+1}}$ 및 ${\frac {2^{\Omega (n)}}{\log m}}$ $2m^{m+1}\cdot 2^{n^{n+1}}$ $2m^{m+1}\cdot 2^{n^{n+1}}$ + $(\$ }\ $cdot 2^{n^{n+$ 1}) 상태 $2m^{m+1}\cdot 2^{n^{n+1}}$ , "지라스코프"^[29] 참조.

클린 별

${\frac {3}{4}}2^{n}$ : $($ { $4}}2^{$ n ${\frac {3}{4}}2^{n}$ }) 상태,^[19] "마슬롭과^[18] 유", "주앙과 살로마아" 참조.
NFA: $n+1$ + $(style$ n $+1}$ 상태 $n+1$ 표시, Holzer 및 Kutrib ^[20]참조).
UFA: $($ 주 ${\frac {3}{4}}2^{n}$ (Jirasek, Jiraskova 및 Sebej ^[21]참조).
$($ { $frac {3}$ {4 $}$ $2^{n}개$ 주), '지라섹', '지라스코바', '사바리'^[22] 참조.
2DFA: ${\frac {1}{n}}2^{{\frac {n}{2}}-1}$ ${\frac {1}{n}}2^{{\frac {n}{2}}-1}$ ${\frac {1}{n}}2^{{\frac {n}{2}}-1}$ 2 - ${\frac {1}{n}}2^{{\frac {n}{2}}-1}$ {\ $displaystyle {1}$ {\ $frac {n} 2^{\$ frac ${n$ }}- $2^{O(n^{n+1})}$ 및 $2^{O(n^{n+1})}$ 2O( $2^{O(n^{n+1})}$ + 1) $2^{O(n^{n+1})}$ { $displaystyle$ 2 $^{O(n^{n+1}}}}}$ 상태 ${\frac {1}{n}}2^{{\frac {n}{2}}-1}$ $2^{O(n^{n+1})}$ , "지라스코바 및 Okhotin"^[29] 참조.

반전

DFA: ${$ 2 $^{n}$ 개 $2^{n}$ 주, 미르킨,^[30] 레이스,^[31] 유, 주앙, 살로마아 ^[19]참조.
NFA: $n+1$ + $(style$ n $+1}$ 상태 $n+1$ 표시, Holzer 및 Kutrib ^[20]참조).
UFA: $\displaystyle$ n $.$
$(스타일$ 2n $+1$ 주(지라섹, 지라스코바 및 사바리 ^[22]참조).
2DFA: n $n+1$ + $({displaystyle$ n $+1$ ~ $n+2$ + $({displaystyle$ n $+2})$ 상태 $n+2$ $n+1$ 에서 지라스코바와 ^[29]Okhotin을 참조하십시오.

단항 알파벳에 대한 유한 오토마타

Chrobak이 ^[32]개척한 1글자(단일) 알파벳을 가진 유한 오토마타의 상태 복잡성은 여러 글자의 경우와 다릅니다.

$g(n)=e^{\Theta ({\sqrt {n\ln n}})}$ ( $g(n)=e^{\Theta ({\sqrt {n\ln n}})}$ n ) $g(n)=e^{\Theta ({\sqrt {n\ln n}})}$ $g(n)=e^{\Theta ({\sqrt {n\ln n}})}$ ( $g(n)=e^{\Theta ({\sqrt {n\ln n}})}$ ln $){$ $displaystyle$ g $(n$ ) = e $^{\$ $Theta({\sqrt {n\ln$ n $}}})$ 는 $g(n)=e^{\Theta ({\sqrt {n\ln n}})}$ Landau의 함수입니다.

모델 간 변환

한 글자 알파벳의 경우, 다른 유형의 유한 오토마타 간 변환이 일반적인 경우보다 더 효율적일 수 있습니다.

NFA에서 DFA: $g(n)+O(n^{2})$ ( $g(n)+O(n^{2})$ ) + $g(n)+O(n^{2})$ ( $g(n)+O(n^{2})$ ) { $displaystyle$ g ( $n$ ) + $O$ ( $n$ ^ {2 $}$ }상태 $g(n)+O(n^{2})$ , Chrobak ^[32]참조.
2DFA에서 DFA: $g(n)+O(n)$ ( $g(n)+O(n)$ ) + $g(n)+O(n)$ ( $g(n)+O(n)$ n $g(n)+O(n)$ ) { $displaystyle$ g ( $n$ ) + $O$ ( $n$ ) }상태 $g(n)+O(n)$ (Chrobak^[32], Kunc 및 Okhotin ^[33]참조).
2NFA에서 DFA: $O(g(n))$ ( $O(g(n))$ ) （ $displaystyle$ O ( $g$ ( $n$ ) $O(g(n))$ ） } 。메레게티와 $O(g(n))$ 피기지니를 참조해 주세요.게퍼트, 메레게티,^[35] 피기지니.^[34]
NFA에서 2DFA: 최대 $O(n^{2})$ 2 $)(\displaystyle$ O $(n^{2})$ 상태에서는 $O(n^{2})$ Chrobak을 ^[32]참조하십시오.
2NFA~2DFA: $n^{O(\log n)}$ $n^{O(\log n)}$ 의 O $n^{O(\log n)}$ n $){$ n $^{O(\log$ n)}}개 $n^{O(\log n)}$ 상태. 사비치의 정리법을 구현함으로써 증명되었다.게퍼트, 메레게티 및 피기지니를 ^[35]참조한다.
UFA에서 DFA: $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ ( $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ ( $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ n ) $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ 3 $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ ) { $display style$ e $^$ { \ $Theta({\sqrt[{3}]{n(\ln$ n)^{ $2$ Okhotin을 ^[36]참조하십시오.
NFA에서 UFA: $g(n)+O(n^{2})$ ( $g(n)+O(n^{2})$ ) + $g(n)+O(n^{2})$ ( $g(n)+O(n^{2})$ ) { $displaystyle$ g ( $n$ ) + $O$ ( n^ {2 $}$ ) $g(n)+O(n^{2})$ 。「 Okhotin ^[36]」를 참조해 주세요.

유니언

DFA: $mn$ \ $displaystyle$ mn $.$ "Yu, Zhuang 및 Salomaa"^[19] 참조.
NFA: $m+n+1$ + $m+n+1$ + $({style$ m $+n+1$ } 상태 $m+n+1$ , Holzer 및 Kutrib ^[20]참조).
2DFA: m $m+n$ + $m+n$ ({ $displaystyle$ m + $n$ } ~ $2m+n+4$ m + $2m+n+4$ + $2m+n+4$ ({ $displaystyle 2 m$ + n + $4$ }) $m+n$ 에서 $2m+n+4$ Kunc와 Okhotin을 ^[23]참조해 주세요.
2NFA: $m+n$ + $m+n$ \ $style$ m + n \ style $m+n$ m + $n$ , 、「 Kunc and Okhotin ^[24]」를 참조해 주세요.

교차로

DFA: $mn$ \ $displaystyle$ mn $.$ "Yu, Zhuang 및 Salomaa"^[19] 참조.
NFA: $\displaystyle$ mn $.$ Holzer와 ^[20]Kutrib을 참조하십시오.
2DFA: $m+n$ m + $m+n$ ({ $displaystyle$ m $+n$ ~ $m+n+1$ m + $m+n+1$ + $({displaystyle$ m $+n+1})$ 상태 $m+n+1$ $m+n+1$ 에서 Kunc 및 Okhotin을 ^[23]참조하십시오.
2NFA: $m+n$ m + $m+n$ ({ $displaystyle$ m $+n$ ~ $m+n+1$ + $m+n+1$ + $({displaystyle$ m $+n+1})$ 상태 $m+n+1$ $m+n$ 에서 Kunc 및 Okhotin을 ^[24]참조하십시오.

보완

$displaystyle n$
NFA: $g(n)+O(n^{2})$ ( $g(n)+O(n^{2})$ n $g(n)+O(n^{2})$ ) + $g(n)+O(n^{2})$ ( $g(n)+O(n^{2})$ 2 $g(n)+O(n^{2})$ ) { $displaystyle$ g ( $n$ ) + $O$ ( $n$ ^ {2 $}$ } }상태입니다 $g(n)+O(n^{2})$ .「 Holzer and Kutrib ^[20]」를 참조해 주세요.
UFA: $n^{(\log \log \log n)^{\Theta (1)}}$ n개 $n^{(\log \log \log n)^{\Theta (1)}}$ ( $n^{(\log \log \log n)^{\Theta (1)}}$ log $n^{(\log \log \log n)^{\Theta (1)}}$ ) $n^{(\log \log \log n)^{\Theta (1)}}$ n ) $n^{(\log \log \log n)^{\Theta (1)}}$ $n^{(\log \log \log n)^{\Theta (1)}}$ $1$ ）{ $display$ n $^{$ ( \ $log$ \ $log$ \ $log$ n $)^{$ \ \ \ \ \ \ log n ) $Theta (1)}}}$ 은 $n^{(\log \log \log n)^{\Theta (1)}}$ (는) ^[37]Raskin을 참조하고, 최대 $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ ( n $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ ( $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ 3 $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ n $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ ) $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ 3 $){$ $display style$ e $^$ { \ $Theta({\sqrt[{3}]{n(\ln$ n)^{ $2}}})}}}}}$ 상태 $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ . Okhotin을 ^[36]참조하십시오.
2DFA: $이상$ $2n+3개$ $2n+3$ 의 상태(Kunc 및 Okhotin $2n+3$ ^[23]참조).
2NFA: 최소 $n개$ $O(n^{8})$ 최대 O개 $n 8개)$ 상태 $.$ 상한은 이머만-제레프세니 정리 방법을 구현하는 것이다(제퍼트, 메레게티 및 ^[28]피기즈니 참조).

연결

DFA: $mn$ \ $displaystyle$ mn $.$ "Yu, Zhuang 및 Salomaa"^[19] 참조.
NFA: m $m+n-1$ + $m+n-1$ - $m+n-1$ ({ $displaystyle$ m $+$ $m+n$ $})$ ~ $m+n$ m $m+n$ + n({ $displaystyle m+$ n $m+n$ }) $m+n$ $m+n-1$ , 「Holzer and ^[20]Kutrib」를 참조해 주세요.
2DFA: $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ ( ( $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ m + $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ n ) $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ ( $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ + $){$ $display style$ e $^$ { \ $Theta(\sqrt {(m+n)\log(m+n)})$ }}개 $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ 주(Kunc 및 ^[23]Okhotin 참조 $).$
2NFA: $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ ( ( $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ m + $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ n ) $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ ( $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ + $){$ $display style$ e $^$ { \ $Theta(\sqrt {(m+n)\log(m+n)})$ }}개 $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ 주(Kunc 및 ^[23]Okhotin 참조 $).$

클린 별

DFA $(n-1)^{2}+1$ ( $(n-1)^{2}+1$ - $(n-1)^{2}+1$ ) $(n-1)^{2}+1$ 2 + $(n-1)^{2}+1$ ({ $displaystyle (n-1)^{2}+1}$ 상태 $(n-1)^{2}+1$ (Yu, Zhuang 및 Salomaa ^[19]참조).
NFA: $n+1$ + $(style$ n $+1}$ 상태 $n+1$ 표시, Holzer 및 Kutrib ^[20]참조).
UFA $(n-1)^{2}+1$ ( $(n-1)^{2}+1$ - $(n-1)^{2}+1$ ) $(n-1)^{2}+1$ 2 + $(n-1)^{2}+1$ $({displaystyle (n-1)^{2}+1}$ 상태 $(n-1)^{2}+1$ (Okhotin ^[36]참조).
2DFA: $\Theta ((g(n))^{2})$ ( $\Theta ((g(n))^{2})$ ( $\Theta ((g(n))^{2})$ ( n $\Theta ((g(n))^{2})$ ) ) $\Theta ((g(n))^{2})$ $){$ $displaystyle$ \ $Theta$ ( ( ( $g$ ( $n$ )^{2} ) $\Theta ((g(n))^{2})$ }상태입니다 $\Theta ((g(n))^{2})$ .「 Kunc and Okhotin ^[23]」를 참조해 주세요.
2NFA: $\Theta (g(n))$ ( $\Theta (g(n))$ ( $\Theta (g(n))$ ) $\Theta (g(n))$ \ $displaystyle$ \ $Theta ( g$ ( $n$ ) } 。상태는 $\Theta (g(n))$ Kunc 및 Okhotin을 ^[23]참조하십시오.

추가 정보

국가의 복잡성에 대한 조사는 Holzer와 Kutrib과^[38]^[39] Gao 등에 의해 작성되었다.^[40]

상태 복잡성에 대한 새로운 연구는 일반적으로 공식 시스템의 기술 복잡성(DCFS)에 관한 연례 워크숍, 자동 시스템의 구현 및 적용에 관한 회의(CIAA) 및 이론 컴퓨터 과학에 관한 다양한 회의에서 발표됩니다.

레퍼런스

^ Rabin, M. O.; Scott, D. (1959). "Finite Automata and Their Decision Problems". IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. ISSN 0018-8646.
^ Lupanov, Oleg B. (1963). "A comparison of two types of finite sources". Problemy Kibernetiki. 9: 321–326.
^ ^a ^b Leung, Hing (2005). "Descriptional complexity of NFA of different ambiguity". International Journal of Foundations of Computer Science. 16 (5): 975–984. doi:10.1142/S0129054105003418. ISSN 0129-0541.
^ ^a ^b Schmidt, Erik M. (1978). Succinctness of Description of Context-Free, Regular and Unambiguous Languages (Ph.D.). Cornell University.
^ Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimal simulation of self-verifying automata by deterministic automata". Information and Computation. 209 (3): 528–535. doi:10.1016/j.ic.2010.11.017. ISSN 0890-5401.
^ ^a ^b ^c Kapoutsis, Christos (2005). "Removing Bidirectionality from Nondeterministic Finite Automata". Mathematical Foundations of Computer Science 2005. Lecture Notes in Computer Science. Vol. 3618. pp. 544–555. doi:10.1007/11549345_47. ISBN 978-3-540-28702-5. ISSN 0302-9743.
^ Shepherdson, J. C. (1959). "The Reduction of Two-Way Automata to One-Way Automata". IBM Journal of Research and Development. 3 (2): 198–200. doi:10.1147/rd.32.0198. ISSN 0018-8646.
^ Moore, F.R. (1971). "On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata". IEEE Transactions on Computers. C-20 (10): 1211–1214. doi:10.1109/T-C.1971.223108. ISSN 0018-9340. S2CID 206618275.
^ Birget, Jean-Camille (1993). "State-complexity of finite-state devices, state compressibility and incompressibility". Mathematical Systems Theory. 26 (3): 237–269. doi:10.1007/BF01371727. ISSN 0025-5661. S2CID 20375279.
^ Vardi, Moshe Y. (1989). "A note on the reduction of two-way automata to one-way automata". Information Processing Letters. 30 (5): 261–264. CiteSeerX 10.1.1.60.464. doi:10.1016/0020-0190(89)90205-6. ISSN 0020-0190.
^ Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. ISSN 0004-5411. S2CID 238863413.
^ Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Constructions for alternating finite automata∗". International Journal of Computer Mathematics. 35 (1–4): 117–132. doi:10.1080/00207169008803893. ISSN 0020-7160.
^ Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Alternating Pushdown and Stack Automata". SIAM Journal on Computing. 13 (1): 135–155. doi:10.1137/0213010. ISSN 0097-5397.
^ Geffert, Viliam; Okhotin, Alexander (2014). Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata. Lecture Notes in Computer Science. Vol. 8634. pp. 291–302. doi:10.1007/978-3-662-44522-8_25. ISBN 978-3-662-44521-1. ISSN 0302-9743.
^ Sakoda, William J.; Sipser, Michael (1978). "Nondeterminism and the Size of Two Way Finite Automata". Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78. STOC 1978. ACM. pp. 275–286. doi:10.1145/800133.804357.
^ Berman, Piotr; Lingas, Andrzej (1977). On the complexity of regular languages in terms of finite automata. Vol. Report 304. Polish Academy of Sciences.
^ Kapoutsis, Christos A. (2014). "Two-Way Automata Versus Logarithmic Space". Theory of Computing Systems. 55 (2): 421–447. doi:10.1007/s00224-013-9465-0. S2CID 14808151.
^ ^a ^b ^c ^d ^e Maslov, A. N. (1970). "Estimates of the number of states of finite automata". Soviet Mathematics - Doklady. 11: 1373–1375.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai (1994). "The state complexities of some basic operations on regular languages". Theoretical Computer Science. 125 (2): 315–328. doi:10.1016/0304-3975(92)00011-F. ISSN 0304-3975.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Holzer, Markus; Kutrib, Martin (2003). "Nondeterministic descriptional complexity of regular languages". International Journal of Foundations of Computer Science (Submitted manuscript). 14 (6): 1087–1102. doi:10.1142/S0129054103002199. ISSN 0129-0541.
^ ^a ^b ^c ^d Jirásek, Jozef; Jirásková, Galina; Šebej, Juraj (2016). Operations on Unambiguous Finite Automata. Lecture Notes in Computer Science. Vol. 9840. pp. 243–255. doi:10.1007/978-3-662-53132-7_20. ISBN 978-3-662-53131-0. ISSN 0302-9743.
^ ^a ^b ^c ^d ^e Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alexander (2015). Computer Science -- Theory and Applications. Lecture Notes in Computer Science. Vol. 9139. pp. 231–261. doi:10.1007/978-3-319-20297-6_16. ISBN 978-3-319-20296-9. ISSN 0302-9743.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Kunc, Michal; Okhotin, Alexander (2012). "State complexity of operations on two-way finite automata over a unary alphabet". Theoretical Computer Science. 449: 106–118. doi:10.1016/j.tcs.2012.04.010. ISSN 0304-3975.
^ ^a ^b ^c ^d Kunc, Michal; Okhotin, Alexander (2011). "State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata". Fundamenta Informaticae. 110 (1–4): 231–239. doi:10.3233/FI-2011-540.
^ Birget, Jean-Camille (1993). "Partial orders on words, minimal elements of regular languages, and state complexity". Theoretical Computer Science. 119 (2): 267–291. doi:10.1016/0304-3975(93)90160-U. ISSN 0304-3975.
^ Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (12 February 2022). "Lower Bounds for Unambiguous Automata via Communication Complexity". arXiv:2109.09155 [cs.FL].
^ Indzhev, Emil; Kiefer, Stefan (1 August 2022). "On complementing unambiguous automata and graphs with many cliques and cocliques". Information Processing Letters. 177: 106270. doi:10.1016/j.ipl.2022.106270. ISSN 0020-0190. S2CID 234741832. Retrieved 29 May 2022.
^ ^a ^b Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007). "Complementing two-way finite automata". Information and Computation. 205 (8): 1173–1187. doi:10.1016/j.ic.2007.01.008. ISSN 0890-5401.
^ ^a ^b ^c Jirásková, Galina; Okhotin, Alexander (2008). On the State Complexity of Operations on Two-Way Finite Automata. Lecture Notes in Computer Science. Vol. 5257. pp. 443–454. doi:10.1007/978-3-540-85780-8_35. ISBN 978-3-540-85779-2. ISSN 0302-9743.
^ Mirkin, Boris G. (1966). "On dual automata". Cybernetics. 2: 6–9. doi:10.1007/bf01072247. S2CID 123186223.
^ Leiss, Ernst (1985). "Succinct representation of regular languages by boolean automata II". Theoretical Computer Science. 38: 133–136. doi:10.1016/0304-3975(85)90215-4. ISSN 0304-3975.
^ ^a ^b ^c ^d Chrobak, Marek (1986). "Finite automata and unary languages". Theoretical Computer Science. 47: 149–158. doi:10.1016/0304-3975(86)90142-8. ISSN 0304-3975.
^ Kunc, Michal; Okhotin, Alexander (2011). Developments in Language Theory. Lecture Notes in Computer Science. Vol. 6795. pp. 324–336. CiteSeerX 10.1.1.616.8835. doi:10.1007/978-3-642-22321-1_28. ISBN 978-3-642-22320-4. ISSN 0302-9743.
^ Mereghetti, Carlo; Pighizzini, Giovanni (2001). "Optimal Simulations between Unary Automata". SIAM Journal on Computing. 30 (6): 1976–1992. doi:10.1137/S009753979935431X. hdl:2434/35121. ISSN 0097-5397.
^ ^a ^b Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2003). "Converting two-way nondeterministic unary automata into simpler automata". Theoretical Computer Science. 295 (1–3): 189–203. doi:10.1016/S0304-3975(02)00403-6. ISSN 0304-3975.
^ ^a ^b ^c ^d Okhotin, Alexander (2012). "Unambiguous finite automata over a unary alphabet". Information and Computation. 212: 15–36. doi:10.1016/j.ic.2012.01.003. ISSN 0890-5401.
^ Raskin, Michael (2018). "A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton". Proc. ICALP 2018. pp. 138:1–138:11. doi:10.4230/LIPIcs.ICALP.2018.138.
^ Holzer, Markus; Kutrib, Martin (2009). "Nondeterministic finite automata — recent results on the descriptional and computational complexity". International Journal of Foundations of Computer Science. 20 (4): 563–580. doi:10.1142/S0129054109006747. ISSN 0129-0541.
^ Holzer, Markus; Kutrib, Martin (2011). "Descriptional and computational complexity of finite automata—A survey". Information and Computation. 209 (3): 456–470. doi:10.1016/j.ic.2010.11.013. ISSN 0890-5401.
^ Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng (2015). "A Survey on Operational State Complexity". arXiv:1509.03254v1 [cs.FL].

[RabinScott1959-1] Rabin, M. O.; Scott, D. (1959). "Finite Automata and Their Decision Problems". IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114. ISSN 0018-8646.

[2] Lupanov, Oleg B. (1963). "A comparison of two types of finite sources". Problemy Kibernetiki. 9: 321–326.

[Leung2005-3] Leung, Hing (2005). "Descriptional complexity of NFA of different ambiguity". International Journal of Foundations of Computer Science. 16 (5): 975–984. doi:10.1142/S0129054105003418. ISSN 0129-0541.

[Schmidt1978-4] Schmidt, Erik M. (1978). Succinctness of Description of Context-Free, Regular and Unambiguous Languages (Ph.D.). Cornell University.

[JiráskováPighizzini2011-5] Jirásková, Galina; Pighizzini, Giovanni (2011). "Optimal simulation of self-verifying automata by deterministic automata". Information and Computation. 209 (3): 528–535. doi:10.1016/j.ic.2010.11.017. ISSN 0890-5401.

[Kapoutsis2005-6] Kapoutsis, Christos (2005). "Removing Bidirectionality from Nondeterministic Finite Automata". Mathematical Foundations of Computer Science 2005. Lecture Notes in Computer Science. Vol. 3618. pp. 544–555. doi:10.1007/11549345_47. ISBN 978-3-540-28702-5. ISSN 0302-9743.

[Shepherdson1959-7] Shepherdson, J. C. (1959). "The Reduction of Two-Way Automata to One-Way Automata". IBM Journal of Research and Development. 3 (2): 198–200. doi:10.1147/rd.32.0198. ISSN 0018-8646.

[Moore1971-8] Moore, F.R. (1971). "On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata". IEEE Transactions on Computers. C-20 (10): 1211–1214. doi:10.1109/T-C.1971.223108. ISSN 0018-9340. S2CID 206618275.

[Birget1993a-9] Birget, Jean-Camille (1993). "State-complexity of finite-state devices, state compressibility and incompressibility". Mathematical Systems Theory. 26 (3): 237–269. doi:10.1007/BF01371727. ISSN 0025-5661. S2CID 20375279.

[Vardi1989-10] Vardi, Moshe Y. (1989). "A note on the reduction of two-way automata to one-way automata". Information Processing Letters. 30 (5): 261–264. CiteSeerX 10.1.1.60.464. doi:10.1016/0020-0190(89)90205-6. ISSN 0020-0190.

[ChandraKozen1981-11] Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. ISSN 0004-5411. S2CID 238863413.

[FellahJürgensen1990-12] Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Constructions for alternating finite automata∗". International Journal of Computer Mathematics. 35 (1–4): 117–132. doi:10.1080/00207169008803893. ISSN 0020-7160.

[LadnerLipton1984-13] Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Alternating Pushdown and Stack Automata". SIAM Journal on Computing. 13 (1): 135–155. doi:10.1137/0213010. ISSN 0097-5397.

[GeffertOkhotin2014-14] Geffert, Viliam; Okhotin, Alexander (2014). Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata. Lecture Notes in Computer Science. Vol. 8634. pp. 291–302. doi:10.1007/978-3-662-44522-8_25. ISBN 978-3-662-44521-1. ISSN 0302-9743.

[15] Sakoda, William J.; Sipser, Michael (1978). "Nondeterminism and the Size of Two Way Finite Automata". Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78. STOC 1978. ACM. pp. 275–286. doi:10.1145/800133.804357.

[16] Berman, Piotr; Lingas, Andrzej (1977). On the complexity of regular languages in terms of finite automata. Vol. Report 304. Polish Academy of Sciences.

[17] Kapoutsis, Christos A. (2014). "Two-Way Automata Versus Logarithmic Space". Theory of Computing Systems. 55 (2): 421–447. doi:10.1007/s00224-013-9465-0. S2CID 14808151.

[Maslov-18] Maslov, A. N. (1970). "Estimates of the number of states of finite automata". Soviet Mathematics - Doklady. 11: 1373–1375.

[YuZhuang1994-19] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai (1994). "The state complexities of some basic operations on regular languages". Theoretical Computer Science. 125 (2): 315–328. doi:10.1016/0304-3975(92)00011-F. ISSN 0304-3975.

[HolzerKutrib2003-20] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Holzer, Markus; Kutrib, Martin (2003). "Nondeterministic descriptional complexity of regular languages". International Journal of Foundations of Computer Science (Submitted manuscript). 14 (6): 1087–1102. doi:10.1142/S0129054103002199. ISSN 0129-0541.

[JirásekJirásková2016-21] Jirásek, Jozef; Jirásková, Galina; Šebej, Juraj (2016). Operations on Unambiguous Finite Automata. Lecture Notes in Computer Science. Vol. 9840. pp. 243–255. doi:10.1007/978-3-662-53132-7_20. ISBN 978-3-662-53131-0. ISSN 0302-9743.

[JirásekJirásková2015-22] Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alexander (2015). Computer Science -- Theory and Applications. Lecture Notes in Computer Science. Vol. 9139. pp. 231–261. doi:10.1007/978-3-319-20297-6_16. ISBN 978-3-319-20296-9. ISSN 0302-9743.

[KuncOkhotin2012-23] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ Kunc, Michal; Okhotin, Alexander (2012). "State complexity of operations on two-way finite automata over a unary alphabet". Theoretical Computer Science. 449: 106–118. doi:10.1016/j.tcs.2012.04.010. ISSN 0304-3975.

[KuncOkhotin2011-24] Kunc, Michal; Okhotin, Alexander (2011). "State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata". Fundamenta Informaticae. 110 (1–4): 231–239. doi:10.3233/FI-2011-540.

[Birget1993b-25] Birget, Jean-Camille (1993). "Partial orders on words, minimal elements of regular languages, and state complexity". Theoretical Computer Science. 119 (2): 267–291. doi:10.1016/0304-3975(93)90160-U. ISSN 0304-3975.

[GoosKieferYuan2022-26] Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (12 February 2022). "Lower Bounds for Unambiguous Automata via Communication Complexity". arXiv:2109.09155 [cs.FL].

[27] Indzhev, Emil; Kiefer, Stefan (1 August 2022). "On complementing unambiguous automata and graphs with many cliques and cocliques". Information Processing Letters. 177: 106270. doi:10.1016/j.ipl.2022.106270. ISSN 0020-0190. S2CID 234741832. Retrieved 29 May 2022.

[GeffertMereghetti2007-28] Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007). "Complementing two-way finite automata". Information and Computation. 205 (8): 1173–1187. doi:10.1016/j.ic.2007.01.008. ISSN 0890-5401.

[JiráskováOkhotin2008-29] Jirásková, Galina; Okhotin, Alexander (2008). On the State Complexity of Operations on Two-Way Finite Automata. Lecture Notes in Computer Science. Vol. 5257. pp. 443–454. doi:10.1007/978-3-540-85780-8_35. ISBN 978-3-540-85779-2. ISSN 0302-9743.

[Mirkin1966-30] Mirkin, Boris G. (1966). "On dual automata". Cybernetics. 2: 6–9. doi:10.1007/bf01072247. S2CID 123186223.

[Leiss1985-31] Leiss, Ernst (1985). "Succinct representation of regular languages by boolean automata II". Theoretical Computer Science. 38: 133–136. doi:10.1016/0304-3975(85)90215-4. ISSN 0304-3975.

[Chrobak1986-32] Chrobak, Marek (1986). "Finite automata and unary languages". Theoretical Computer Science. 47: 149–158. doi:10.1016/0304-3975(86)90142-8. ISSN 0304-3975.

[KuncOkhotin2011b-33] Kunc, Michal; Okhotin, Alexander (2011). Developments in Language Theory. Lecture Notes in Computer Science. Vol. 6795. pp. 324–336. CiteSeerX 10.1.1.616.8835. doi:10.1007/978-3-642-22321-1_28. ISBN 978-3-642-22320-4. ISSN 0302-9743.

[MereghettiPighizzini2001-34] Mereghetti, Carlo; Pighizzini, Giovanni (2001). "Optimal Simulations between Unary Automata". SIAM Journal on Computing. 30 (6): 1976–1992. doi:10.1137/S009753979935431X. hdl:2434/35121. ISSN 0097-5397.

[GeffertMereghetti2003-35] Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2003). "Converting two-way nondeterministic unary automata into simpler automata". Theoretical Computer Science. 295 (1–3): 189–203. doi:10.1016/S0304-3975(02)00403-6. ISSN 0304-3975.

[Okhotin2012-36] Okhotin, Alexander (2012). "Unambiguous finite automata over a unary alphabet". Information and Computation. 212: 15–36. doi:10.1016/j.ic.2012.01.003. ISSN 0890-5401.

[Raskin2018-37] Raskin, Michael (2018). "A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton". Proc. ICALP 2018. pp. 138:1–138:11. doi:10.4230/LIPIcs.ICALP.2018.138.

[HolzerKutrib2009-38] Holzer, Markus; Kutrib, Martin (2009). "Nondeterministic finite automata — recent results on the descriptional and computational complexity". International Journal of Foundations of Computer Science. 20 (4): 563–580. doi:10.1142/S0129054109006747. ISSN 0129-0541.

[HolzerKutrib2011-39] Holzer, Markus; Kutrib, Martin (2011). "Descriptional and computational complexity of finite automata—A survey". Information and Computation. 209 (3): 456–470. doi:10.1016/j.ic.2010.11.013. ISSN 0890-5401.

[40] Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng (2015). "A Survey on Operational State Complexity". arXiv:1509.03254v1 [cs.FL].

[1]

[2]

[4]

[3]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[19]

[18]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[28]

[29]

[30]

[31]

[32]

[33]

[35]

[34]

[36]

[37]

[38]

[39]

[40]

Search

상태 복잡성

네임스페이스

더

목차

유한 오토마타의 변형 간 변환

2DFA 대 2NFA 문제와 로그 공간

유한 오토마타에 대한 운영의 복잡성 상태

유니언

교차로

보완

연결

클린 별

반전

단항 알파벳에 대한 유한 오토마타

모델 간 변환

유니언

교차로

보완

연결

클린 별

추가 정보

레퍼런스