# Uniform _vs._ Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
## 2 Uniform and Nonuniform Membership Complexity  
In formal language theory, three of the fundamental concepts are languages, language formalisms, and language classes. By a language formalism we mean a class of language representations. Examples of language formalisms are deterministic finite automata, regular expressions, CFGs, LCFRSs, _etc._ Each formalism also gives rise to a language class, _i.e._, the class of all languages that can be represented by the formalism. For both deterministic finite automata and regular expressions this class is the regular languages. For CFGs, it is the context-free languages.  
The difference between the uniform and the nonuniform complexity of a formal language membership problem for a certain formalism is whether we consider the language description as part of the input or not. In the uniform case we do, but in the nonuniform case we do not.  
**Definition 1**.: Let \(\mathcal{L}\) be a formal language over alphabet \(\Sigma\). The membership problem for \(\mathcal{L}\) is the following:  
* **Input:** A string \(w\in\Sigma^{*}\).
* **Question:** Does \(w\) belong to \(\mathcal{L}\)?  
The above definition coincides with the complexity-theoretical concept of a decision problem. When we talk about the nonuniform complexity for a formalism, we are actually referring to a whole class of decision problems--one for each language in the corresponding language class.  
In the uniform case, however, we consider the actual language representation as a part of the input. This means that when we talk about the uniform complexity for a formalism, we are only referring to a single decision problem:  
**Definition 2**.: Let \(\mathcal{F}\) be a language formalism. The uniform membership problem for \(\mathcal{F}\) is the following:  
* **Input:** A language representation \(R\in\mathcal{F}\) and a string \(w\).
* **Question:** Does \(w\) belong to \(\mathcal{L}(F)\)?  
It may seem strange to talk about the nonuniform complexity, but there are actually a number of fields in computer science where we come across similar notions. In database theory, we often use the notions of query complexity, data complexity and combined complexity. Here, the query complexity and the data complexity describe how the difficulty of evaluating a query over a database grows with the size of the query and the database, respectively. They are both nonuniform complexity measures. The combined complexity, that takes both the query and the database into account, is a uniform measure. Similarly, in model checking, we can talk about the formula complexity, the model complexity and the combined complexity. We know that model checking for linear temporal logic (LTL) over Kripke structures is linear in the size of the model, but exponential in the size of the formula. For a formula \(\phi\) and a model \(M\), the complexity of the best known algorithms is \(2^{\mathcal{O}(|\phi|)}\cdot\mathcal{O}(|M|)\).  
In formal languages, we often say things like \"the membership problem for nondeterministic finite automata is linear\". In the terminology presented above, this is not entirely correct. It would be more appropriate to say that the nonuniform membership problem for regular languages is linear or that the uniform membership problem for nondeterministic finite automata is linear in the size of the input string.  
It is crucially important for what follows that when we say that the nonuniform membership problem for a formalism is solvable in polynomial time, this only means that for each language that can be represented by the formalism, the corresponding membership problem is polynomial. It does not mean that there is one single polynomial that bounds the amount of time it takes to solve the membership problems for all the languages the formalism can represent.