| Worst-Case | Given a complexity language measure $m$ and an operation $\circ$ over languages $L_1, \ldots, L_k$, it is the worst-case $m$ 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$. |
| 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 state complexity of a regular language $\cal{L}$, denoted by $sc(\cal{L})$, is the number of states of its minimal DFA. | DFA |
| Nondeterministic Transition Complexity | The nondeterministic transition complexity of $\cal{L}$ (also called transition complexity), denoted by $tc(\mathcal{L})$, is the smallest number of transitions of an NFA that recognizes $\cal{L}$. | NFA |
| Nondeterministic State Complexity | The nondeterministic state complexity of a language $\cal{L}$, denoted by $nsc(\cal{L})$, is the number of states of one of its minimal NFAs. | 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 |