## Worst-Case on Regular languages Click on a function to get more detailed information

Filter:

Operation State Complexity
$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$
$L^b$ $(m-2)2^{m-2}+3$ , if $m \ge 4$
for $\mid \Sigma \mid$ $>$ $3$
$L_1L_2$ $m$ , if $m>0, n=1$
for $\mid \Sigma \mid$ $>$ $0$ witnesses for: $m>0, n=1$
$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$
$mn$ , if $m>0, n>0$
for $\mid \Sigma \mid$ $=$ $1$ witnesses for: $(m,n)=1$
$\overline{L}$ $m$
for $\mid \Sigma \mid$ $>$ $0$
$L^{CS}$ $(m2^m-2^{m-1})^m$
for $\mid \Sigma \mid$ $>$ $0$
$m$
for $\mid \Sigma \mid$ $=$ $1$
$2^{\Theta(m^2)}$
for $\mid \Sigma \mid$ $=$ $2$
$2^{m^2+m\log m-O(m)}$
for $\mid \Sigma \mid$ $>$ $3$
$2^{\Theta(m^2)}$
for $\mid \Sigma \mid$ $=$ $3$
$L_1 \setminus L_2$ $mn$
for $\mid \Sigma \mid$ $>$ $1$
$L^\sqsubseteq$ $(m-2)2^{m-3}+3$ , if $m \ge 4$
for $\mid \Sigma \mid$ $>$ $2$
$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$
$\Sigma^\star L$ $2^{m-1}$
for $\mid \Sigma \mid$ $>$ $1$ witnesses for: $m=1;m>1$
$L_1^{-1} L_2$ $2^m - 1$
for $\mid \Sigma \mid$ $>$ $1$
$w^{-1}L$ $m$
for $\mid \Sigma \mid$ $>$ $0$
$L_1 \odot_\perp L_2$ $m2^{n-1}-2^{n-2}$ , if $m \ge 3,\ n \ge 4$
for $\mid \Sigma \mid$ $>$ $3$
$L^{+}$ $2^{n-1}+2^{n-l-1} - 1$
for $\mid \Sigma \mid$ $>$ $1$
$(m-1)^2$
for $\mid \Sigma \mid$ $=$ $1$
$L^i$ $i m + i + 1$ , if $i \ge 2$
for $\mid \Sigma \mid$ $=$ $1$
$\frac {6m - 3}{8} 4^m - (m - 1)2^m - m$ , if $i = 3$
for $\mid \Sigma \mid$ $>$ $3$
$\Theta(m2^{(i-1)m})$ , if $i\geq 2$
for $\mid \Sigma \mid$ $>$ $5$
$L^\le$ $m+1$
for $\mid \Sigma \mid$ $>$ $1$
$\frac {1}{2} (L)$ $m$
for $\mid \Sigma \mid$ $>$ $0$
$me^{\Theta (\sqrt {m \log m})}$
for $\mid \Sigma \mid$ $>$ $2$
$L^R$ $2^m$ , if $m>0$
for $\mid \Sigma \mid$ $>$ $1$
$m$
for $\mid \Sigma \mid$ $=$ $1$ witnesses for: $m>0$
$L\Sigma^*$ $m$
for $\mid \Sigma \mid$ $>$ $0$
$L_2L_1^{-1}$ $m$
for $\mid \Sigma \mid$ $>$ $0$
$L w^{-1}$ $m$
for $\mid \Sigma \mid$ $>$ $0$
$L_1 \shuffle L_2$ $O (2^{mn}-1)$
for $\mid \Sigma \mid$ $>$ $4$
$L^\star$ $m$ , if $m>1, l=0$
for $\mid \Sigma \mid$ $>$ $0$
$m+1$ , if $m=1$
for $\mid \Sigma \mid$ $>$ $0$
$2^{m-1}+2^{m-l-1}$ , if $m>1, l>0$
for $\mid \Sigma \mid$ $>$ $1$ witnesses for: $m=2;m>2$
$(m-1)^2+1$ , if $m>1$
for $\mid \Sigma \mid$ $=$ $1$ witnesses for: $m=2;m>2$
$L^\preceq$ $(m-1)2^{m-2}+2$ , if $m \ge 4$
for $\mid \Sigma \mid$ $>$ $3$
$L_1\oplus L_2$ $mn$
for $\mid \Sigma \mid$ $>$ $1$
$\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$
$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$
$L_1 \circ L_2$ $O(m3^n - f_1 3^{n-1})$
for $\mid \Sigma \mid$ $>$ $0$
$L^{\circ2}$ $m3^m - 3^{m-1}$
for $\mid \Sigma \mid$ $>$ $1$
$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$
$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$