Worst-Case | Given a complexity language measure $m$ and an operation $\circ$ over languages $L_1, \ldots, L_k$, it is the |

Average-Case | Given a language complexity measure $m$, a probability distribution over the model of computation with measure $m$, and an operation $\circ$ over languages $L_1, \ldots, L_k$, the average-case complexity of a language $L$ resulting from operation $\circ$, considered as a function of the complexity measures of the operands $L_i$, $1\leq i\leq k$ is $\sum_{l} l Prob(m(\circ(L_1,\ldots,L_k))=l,$ where $Prob$ is the probability with respect to the probability distribution. |

State Complexity | The | DFA |

Nondeterministic Transition Complexity | The | NFA |

Nondeterministic State Complexity | The n | NFA |

Incomplete State Complexity | The incomplete state complexity of a regular language $\mathcal{L}$, denoted by isc($\mathcal{L}$), is the number of states of its minimal IDFA. | IDFA |

Deterministic Transition Complexity | The deterministic transition complexity of regular language $\mathcal{L}$, denoted by $dtc(\mathcal{L})$, is the number of transitions of its minimal DFA. One always has $dtc(\mathcal{L}) = |\Sigma|\times sc(\mathcal{L})$. | DFA |

Incomplete Transition Complexity | The incomplete transition complexity of regular language $\mathcal{L}$, denoted by itc($\mathcal{L}$), is the number of transitions of its minimal IDFA. | IDFA |

Syntactic Complexity | The syntactic complexity of a regular language $L$ is the cardinality of the syntactic semigroup of $L$. This is the quotient of $\Sigma^+$ by the Myhill equivalence relation.For any language $L\subseteq \Sigma^*$, define the Myhill congruence $\rightarrow_L$ of $L$ by$ \begin{equation} x \rightarrow_L y \mbox{ if and only if } uxv\in L \Leftrightarrow uyv\in L\mbox { for all } u,v\in\Sigma^*. \end{equation} $ The transition semigroup of a minimal complete DFA $A=(Q,\Sigma,\delta,q_0,F)$ is the semigroup consisting of all the transformations of the set $Q$ by non-empty words over $\Sigma$; the operation is composition of transformations.The syntactic semigroup of $L$ is isomorphic to the transition semigroup of the minimal complete DFA of $L$. | DFA |