## Complexity Kinds

 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.

## Complexity Measures

 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$$$x \rightarrow_L y \mbox{ if and only if } uxv\in L \Leftrightarrow uyv\in L\mbox { for all } u,v\in\Sigma^*.$$$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