Worst-Case on Regular languages

Click on a function to get more detailed information

Filter:

Operation State Complexity
All-Sided Ideal Generated $ L\shuffle \Sigma^\star $ $ 2^{m-2}+1 $ , if $ m\ge 2 $
for $\mid \Sigma \mid$ $ > $ $ m-3 $ witnesses for: $ m=2;m\ge 3 $
Bifix-freeness $ L^b $ $ (m-2)2^{m-2}+3 $ , if $ m \ge 4 $
for $\mid \Sigma \mid$ $ > $ $ 3 $
Catenation $ L_1L_2 $ $ m $ , if $ m>0, n=1 $
for $\mid \Sigma \mid$ $ > $ $ 0 $ witnesses for: $ m>0, n=1 $
Catenation $ m2^n - f_12^{n-1} $ , if $ m\geq 1, n\gt 1, f_1\geq 1 $
for $\mid \Sigma \mid$ $ > $ $ 1 $ witnesses for: $ m=1, n\geq 2;m\geq 2, n\geq 2 $
Catenation $ mn $ , if $ m>0, n>0 $
for $\mid \Sigma \mid$ $ = $ $ 1 $ witnesses for: $ (m,n)=1 $
Complementation $ \overline{L} $ $ m $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Cyclic Shift $ L^{CS} $ $ (m2^m-2^{m-1})^m $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Cyclic Shift $ m $
for $\mid \Sigma \mid$ $ = $ $ 1 $
Cyclic Shift $ 2^{\Theta(m^2)} $
for $\mid \Sigma \mid$ $ = $ $ 2 $
Cyclic Shift $ 2^{m^2+m\log m-O(m)} $
for $\mid \Sigma \mid$ $ > $ $ 3 $
Cyclic Shift $ 2^{\Theta(m^2)} $
for $\mid \Sigma \mid$ $ = $ $ 3 $
Difference $ L_1 \setminus L_2 $ $ mn $
for $\mid \Sigma \mid$ $ > $ $ 1 $
Factor-freeness $ L^\sqsubseteq $ $ (m-2)2^{m-3}+3 $ , if $ m \ge 4 $
for $\mid \Sigma \mid$ $ > $ $ 2 $
Intersection $ L_1\cap L_2 $ $ mn $ , if $ m>0, n>0 $
for $\mid \Sigma \mid$ $ > $ $ 0 $ witnesses for: $ m \geq 1, n \geq 1;m>1,n>1, (m.n)=1 $
Left Ideal Generated $ \Sigma^\star L $ $ 2^{m-1} $
for $\mid \Sigma \mid$ $ > $ $ 1 $ witnesses for: $ m=1;m>1 $
Left quotient $ L_1^{-1} L_2 $ $ 2^m - 1 $
for $\mid \Sigma \mid$ $ > $ $ 1 $
Left quotient by a word $ w^{-1}L $ $ m $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Orthogonal Catenation $ L_1 \odot_\perp L_2 $ $ m2^{n-1}-2^{n-2} $ , if $ m \ge 3,\ n \ge 4 $
for $\mid \Sigma \mid$ $ > $ $ 3 $
Plus $ L^{+} $ $ 2^{n-1}+2^{n-l-1} - 1 $
for $\mid \Sigma \mid$ $ > $ $ 1 $
Plus $ (m-1)^2 $
for $\mid \Sigma \mid$ $ = $ $ 1 $
Power $ L^i $ $ i m + i + 1 $ , if $ i \ge 2 $
for $\mid \Sigma \mid$ $ = $ $ 1 $
Power $ \frac {6m - 3}{8} 4^m - (m - 1)2^m - m $ , if $ i = 3 $
for $\mid \Sigma \mid$ $ > $ $ 3 $
Power $ \Theta(m2^{(i-1)m}) $ , if $ i\geq 2 $
for $\mid \Sigma \mid$ $ > $ $ 5 $
Prefix-freeness $ L^\le $ $ m+1 $
for $\mid \Sigma \mid$ $ > $ $ 1 $
Proportional removals for identity relation $ \frac {1}{2} (L) $ $ m $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Proportional removals for identity relation $ me^{\Theta (\sqrt {m \log m})} $
for $\mid \Sigma \mid$ $ > $ $ 2 $
Reversal $ L^R $ $ 2^m $ , if $ m>0 $
for $\mid \Sigma \mid$ $ > $ $ 1 $
Reversal $ m $
for $\mid \Sigma \mid$ $ = $ $ 1 $ witnesses for: $ m>0 $
Right Ideal Generated $ L\Sigma^* $ $ m $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Right quotient $ L_2L_1^{-1} $ $ m $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Right quotient by a word $ L w^{-1} $ $ m $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Shuffle $ L_1 \shuffle L_2 $ $ O (2^{mn}-1) $
for $\mid \Sigma \mid$ $ > $ $ 4 $
Star $ L^\star $ $ m $ , if $ m>1, l=0 $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Star $ m+1 $ , if $ m=1 $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Star $ 2^{m-1}+2^{m-l-1} $ , if $ m>1, l>0 $
for $\mid \Sigma \mid$ $ > $ $ 1 $ witnesses for: $ m=2;m>2 $
Star $ (m-1)^2+1 $ , if $ m>1 $
for $\mid \Sigma \mid$ $ = $ $ 1 $ witnesses for: $ m=2;m>2 $
Suffix-freeness $ L^\preceq $ $ (m-1)2^{m-2}+2 $ , if $ m \ge 4 $
for $\mid \Sigma \mid$ $ > $ $ 3 $
Symmetric Difference $ L_1\oplus L_2 $ $ mn $
for $\mid \Sigma \mid$ $ > $ $ 1 $
Two-Sided Ideal Generated $ \Sigma^\star L \Sigma^\star $ $ 2^{m-2}+1 $ , if $ m\ge 2 $
for $\mid \Sigma \mid$ $ > $ $ 1 $ witnesses for: $ m=2;m\ge 3 $
Union $ L_1\cup L_2 $ $ mn $ , if $ m>0, n>0 $
for $\mid \Sigma \mid$ $ > $ $ 0 $ witnesses for: $ m \geq 1, n \geq 1;m>1,n>1, (m,n)=1 $
Unique Catenation $ L_1 \circ L_2 $ $ O(m3^n - f_1 3^{n-1}) $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Unique Square $ L^{\circ2} $ $ m3^m - 3^{m-1} $
for $\mid \Sigma \mid$ $ > $ $ 1 $
Unique Star $ L^\circ $ $ O(3^{m-1} + (f + 2)3^{m-f-1} - (2^{m-1} + 2^{m-f-1} - 2)) $
for $\mid \Sigma \mid$ $ > $ $ 0 $
Unique Union $ L_1 \buildrel\circ\over\cup L_2 $ $ mn $
for $\mid \Sigma \mid$ $ > $ $ 1 $
$ sim(L) $
$ _\unlhd L $
$ _\le L $
$ _\preceq L $
$ _\sqsubseteq L $
$ _\Subset L $
$ L $
$ MinGen\Sigma^* $
$ \Sigma^\star MinGen $
$ \Sigma^\star MinGen \Sigma^\star $
$ MinGen \shuffle \Sigma^\star $