text:
2-satisfiability

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

Instances of the 2-satisfiability problem are typically expressed as Boolean formulas of a special type, called conjunctive normal form (2-CNF) or Krom formulas. Alternatively, they may be expressed as a special type of directed graph, the implication graph, which expresses the variables of an instance and their negations as vertices in a graph, and constraints on pairs of variables as directed edges. Both of these kinds of inputs may be solved in linear time, either by a method based on backtracking or by using the strongly connected components of the implication graph. Resolution, a method for combining pairs of constraints to make additional valid constraints, also leads to a polynomial time solution. The 2-satisfiability problems provide one of two major subclasses of the conjunctive normal form formulas that can be solved in polynomial time; the other of the two subclasses is Horn-satisfiability.

2-satisfiability may be applied to geometry and visualization problems in which a collection of objects each have two potential locations and the goal is to find a placement for each object that avoids overlaps with other objects. Other applications include clustering data to minimize the sum of the diameters of the clusters, classroom and sports scheduling, and recovering shapes from information about their cross-sections.

In computational complexity theory, 2-satisfiability provides an example of an NL-complete problem, one that can be solved non-deterministically using a logarithmic amount of storage and that is among the hardest of the problems solvable in this resource bound. The set of all solutions to a 2-satisfiability instance can be given the structure of a median graph, but counting these solutions is #P-complete and therefore not expected to have a polynomial-time solution. Random instances undergo a sharp phase transition from solvable to unsolvable instances as the ratio of constraints to variables increases past 1, a phenomenon conjectured but unproven for more complicated forms of the satisfiability problem. A computationally difficult variation of 2-satisfiability, finding a truth assignment that maximizes the number of satisfied constraints, has an approximation algorithm whose optimality depends on the unique games conjecture, and another difficult variation, finding a satisfying assignment minimizing the number of true variables, is an important test case for parameterized complexity.

Problem representations
A 2-satisfiability problem may be described using a Boolean expression with a special restricted form. It is a conjunction (a Boolean and operation) of clauses, where each clause is a disjunction (a Boolean or operation) of two variables or negated variables. The variables or their negations appearing in this formula are known as literals. For example, the following formula is in conjunctive normal form, with seven variables, eleven clauses, and 22 literals: $$ \begin{align} &(x_0\lor x_2)\land(x_0\lor\lnot x_3)\land(x_1\lor\lnot x_3)\land(x_1\lor\lnot x_4)\land{} \\ &(x_2\lor\lnot x_4)\land{}(x_0\lor \lnot x_5)\land (x_1\lor\lnot x_5)\land (x_2\lor\lnot x_5)\land{} \\ &(x_3\lor x_6)\land (x_4\lor x_6)\land (x_5\lor x_6). \end{align} $$

The 2-satisfiability problem is to find a truth assignment to these variables that makes the whole formula true. Such an assignment chooses whether to make each of the variables true or false, so that at least one literal in every clause becomes true. For the expression shown above, one possible satisfying assignment is the one that sets all seven of the variables to true. Every clause has at least one non-negated variable, so this assignment satisfies every clause. There are also 15 other ways of setting all the variables so that the formula becomes true. Therefore, the 2-satisfiability instance represented by this expression is satisfiable.

Formulas in this form are known as 2-CNF formulas. The "2" in this name stands for the number of literals per clause, and "CNF" stands for conjunctive normal form, a type of Boolean expression in the form of a conjunction of disjunctions. They are also called Krom formulas, after the work of UC Davis mathematician Melven R. Krom, whose 1967 paper was one of the earliest works on the 2-satisfiability problem.

Each clause in a 2-CNF formula is logically equivalent to an implication from one variable or negated variable to the other. For example, the second clause in the example may be written in any of three equivalent ways: $$(x_0\lor\lnot x_3) \;\equiv\; (\lnot x_0\Rightarrow\lnot x_3) \;\equiv\; (x_3\Rightarrow x_0).$$ Because of this equivalence between these different types of operation, a 2-satisfiability instance may also be written in implicative normal form, in which we replace each or clause in the conjunctive normal form by the two implications to which it is equivalent.

A third, more graphical way of describing a 2-satisfiability instance is as an implication graph. An implication graph is a directed graph in which there is one vertex per variable or negated variable, and an edge connecting one vertex to another whenever the corresponding variables are related by an implication in the implicative normal form of the instance. An implication graph must be a skew-symmetric graph, meaning that it has a symmetry that takes each variable to its negation and reverses the orientations of all of the edges.

Algorithms
Several algorithms are known for solving the 2-satisfiability problem. The most efficient of them take linear time.

Resolution and transitive closure
described the following polynomial time decision procedure for solving 2-satisfiability instances.

Suppose that a 2-satisfiability instance contains two clauses that both use the same variable x, but that x is negated in one clause and not in the other. Then the two clauses may be combined to produce a third clause, having the two other literals in the two clauses; this third clause must also be satisfied whenever the first two clauses are both satisfied. This is called resolution. For instance, we may combine the clauses $$(a\lor b)$$ and $$(\lnot b\lor\lnot c)$$ in this way to produce the clause $$(a\lor\lnot c)$$. In terms of the implicative form of a 2-CNF formula, this rule amounts to finding two implications $$\lnot a\Rightarrow b$$ and $$b\Rightarrow \lnot c$$, and inferring by transitivity a third implication $$\lnot a\Rightarrow \lnot c$$.

Krom writes that a formula is consistent if repeated application of this inference rule cannot generate both the clauses $$(x\lor x)$$ and $$ (\lnot x\lor\lnot x)$$, for any variable $$ x$$. As he proves, a 2-CNF formula is satisfiable if and only if it is consistent. For, if a formula is not consistent, it is not possible to satisfy both of the two clauses $$ (x\lor x)$$ and $$(\lnot x\lor\lnot x)$$ simultaneously. And, if it is consistent, then the formula can be extended by repeatedly adding one clause of the form $$ (x\lor x)$$ or $$ (\lnot x\lor\lnot x)$$ at a time, preserving consistency at each step, until it includes such a clause for every variable. At each of these extension steps, one of these two clauses may always be added while preserving consistency, for if not then the other clause could be generated using the inference rule. Once all variables have a clause of this form in the formula, a satisfying assignment of all of the variables may be generated by setting a variable $$ x$$ to true if the formula contains the clause $$ (x\lor x)$$ and setting it to false if the formula contains the clause $$(\lnot x\lor\lnot x)$$.

Krom was concerned primarily with completeness of systems of inference rules, rather than with the efficiency of algorithms. However, his method leads to a polynomial time bound for solving 2-satisfiability problems. By grouping together all of the clauses that use the same variable, and applying the inference rule to each pair of clauses, it is possible to find all inferences that are possible from a given 2-CNF instance, and to test whether it is consistent, in total time $O(n^{3})$, where $n$ is the number of variables in the instance. This formula comes from multiplying the number of variables by the $O(n^{2})$ number of pairs of clauses involving a given variable, to which the inference rule may be applied. Thus, it is possible to determine whether a given 2-CNF instance is satisfiable in time $O(n^{3})$. Because finding a satisfying assignment using Krom's method involves a sequence of $O(n)$ consistency checks, it would take time $O(n^{4})$. quote a faster time bound of $O(n^{2})$ for this algorithm, based on more careful ordering of its operations. Nevertheless, even this smaller time bound was greatly improved by the later linear time algorithms of and.

In terms of the implication graph of the 2-satisfiability instance, Krom's inference rule can be interpreted as constructing the transitive closure of the graph. As observes, it can also be seen as an instance of the Davis–Putnam algorithm for solving satisfiability problems using the principle of resolution. Its correctness follows from the more general correctness of the Davis–Putnam algorithm. Its polynomial time bound follows from the fact that each resolution step increases the number of clauses in the instance, which is upper bounded by a quadratic function of the number of variables.

Limited backtracking
describe a technique involving limited backtracking for solving constraint satisfaction problems with binary variables and pairwise constraints. They apply this technique to a problem of classroom scheduling, but they also observe that it applies to other problems including 2-SAT.

The basic idea of their approach is to build a partial truth assignment, one variable at a time. Certain steps of the algorithms are "choice points", points at which a variable can be given either of two different truth values, and later steps in the algorithm may cause it to backtrack to one of these choice points. However, only the most recent choice can be backtracked over. All choices made earlier than the most recent one are permanent.

Initially, there is no choice point, and all variables are unassigned. At each step, the algorithm chooses the variable whose value to set, as follows:
 * If there is a clause both of whose variables are already set, in a way that falsifies the clause, then the algorithm backtracks to its most recent choice point, undoing the assignments it made since that choice, and reverses the decision made at that choice. If there is no choice point, or if the algorithm has already backtracked over the most recent choice point, then it aborts the search and reports that the input 2-CNF formula is unsatisfiable.
 * If there is a clause in which one of the clause's two variables has already been set, and the clause could still become either true or false, then the other variable is set in a way that forces the clause to become true.
 * In the remaining case, each clause is either guaranteed to become true no matter how the remaining variables are assigned, or neither of its two variables has been assigned yet. In this case the algorithm creates a new choice point and sets any one of the unassigned variables to an arbitrarily chosen value.

Intuitively, the algorithm follows all chains of inference after making each of its choices. This either leads to a contradiction and a backtracking step, or, if no contradiction is derived, it follows that the choice was a correct one that leads to a satisfying assignment. Therefore, the algorithm either correctly finds a satisfying assignment or it correctly determines that the input is unsatisfiable.

Even et al. did not describe in detail how to implement this algorithm efficiently. They state only that by "using appropriate data structures in order to find the implications of any decision", each step of the algorithm (other than the backtracking) can be performed quickly. However, some inputs may cause the algorithm to backtrack many times, each time performing many steps before backtracking, so its overall complexity may be nonlinear. To avoid this problem, they modify the algorithm so that, after reaching each choice point, it begins simultaneously testing both of the two assignments for the variable set at the choice point, spending equal numbers of steps on each of the two assignments. As soon as the test for one of these two assignments would create another choice point, the other test is stopped, so that at any stage of the algorithm there are only two branches of the backtracking tree that are still being tested. In this way, the total time spent performing the two tests for any variable is proportional to the number of variables and clauses of the input formula whose values are permanently assigned. As a result, the algorithm takes linear time in total.

Strongly connected components
found a simpler linear time procedure for solving 2-satisfiability instances, based on the notion of strongly connected components from graph theory.

Two vertices in a directed graph are said to be strongly connected to each other if there is a directed path from one to the other and vice versa. This is an equivalence relation, and the vertices of the graph may be partitioned into strongly connected components, subsets within which every two vertices are strongly connected. There are several efficient linear time algorithms for finding the strongly connected components of a graph, based on depth-first search: Tarjan's strongly connected components algorithm and the path-based strong component algorithm each perform a single depth-first search. Kosaraju's algorithm performs two depth-first searches, but is very simple.

In terms of the implication graph, two literals belong to the same strongly connected component whenever there exist chains of implications from one literal to the other and vice versa. Therefore, the two literals must have the same value in any satisfying assignment to the given 2-satisfiability instance. In particular, if a variable and its negation both belong to the same strongly connected component, the instance cannot be satisfied, because it is impossible to assign both of these literals the same value. As Aspvall et al. showed, this is a necessary and sufficient condition: a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.

This immediately leads to a linear time algorithm for testing satisfiability of 2-CNF formulae: simply perform a strong connectivity analysis on the implication graph and check that each variable and its negation belong to different components. However, as Aspvall et al. also showed, it also leads to a linear time algorithm for finding a satisfying assignment, when one exists. Their algorithm performs the following steps:
 * Construct the implication graph of the instance, and find its strongly connected components using any of the known linear-time algorithms for strong connectivity analysis.
 * Check whether any strongly connected component contains both a variable and its negation. If so, report that the instance is not satisfiable and halt.
 * Construct the condensation of the implication graph, a smaller graph that has one vertex for each strongly connected component, and an edge from component $i$ to component $j$ whenever the implication graph contains an edge $uv$ such that $u$ belongs to component $i$ and $v$ belongs to component $j$. The condensation is automatically a directed acyclic graph and, like the implication graph from which it was formed, it is skew-symmetric.
 * Topologically order the vertices of the condensation. In practice this may be efficiently achieved as a side effect of the previous step, as components are generated by Kosaraju's algorithm in topological order and by Tarjan's algorithm in reverse topological order.
 * For each component in the reverse topological order, if its variables do not already have truth assignments, set all the literals in the component to be true. This also causes all of the literals in the complementary component to be set to false.

Due to the reverse topological ordering and the skew-symmetry, when a literal is set to true, all literals that can be reached from it via a chain of implications will already have been set to true. Symmetrically, when a literal $x$ is set to false, all literals that lead to it via a chain of implications will themselves already have been set to false. Therefore, the truth assignment constructed by this procedure satisfies the given formula, which also completes the proof of correctness of the necessary and sufficient condition identified by Aspvall et al.

As Aspvall et al. show, a similar procedure involving topologically ordering the strongly connected components of the implication graph may also be used to evaluate fully quantified Boolean formulae in which the formula being quantified is a 2-CNF formula.

Conflict-free placement of geometric objects
A number of exact and approximate algorithms for the automatic label placement problem are based on 2-satisfiability. This problem concerns placing textual labels on the features of a diagram or map. Typically, the set of possible locations for each label is highly constrained, not only by the map itself (each label must be near the feature it labels, and must not obscure other features), but by each other: every two labels should avoid overlapping each other, for otherwise they would become illegible. In general, finding a label placement that obeys these constraints is an NP-hard problem. However, if each feature has only two possible locations for its label (say, extending to the left and to the right of the feature) then label placement may be solved in polynomial time. For, in this case, one may create a 2-satisfiability instance that has a variable for each label and that has a clause for each pair of labels that could overlap, preventing them from being assigned overlapping positions. If the labels are all congruent rectangles, the corresponding 2-satisfiability instance can be shown to have only linearly many constraints, leading to near-linear time algorithms for finding a labeling. describe a map labeling problem in which each label is a rectangle that may be placed in one of three positions with respect to a line segment that it labels: it may have the segment as one of its sides, or it may be centered on the segment. They represent these three positions using two binary variables in such a way that, again, testing the existence of a valid labeling becomes a 2-satisfiability problem.

use 2-satisfiability as part of an approximation algorithm for the problem of finding square labels of the largest possible size for a given set of points, with the constraint that each label has one of its corners on the point that it labels. To find a labeling with a given size, they eliminate squares that, if doubled, would overlap another point, and they eliminate points that can be labeled in a way that cannot possibly overlap with another point's label. They show that these elimination rules cause the remaining points to have only two possible label placements per point, allowing a valid label placement (if one exists) to be found as the solution to a 2-satisfiability instance. By searching for the largest label size that leads to a solvable 2-satisfiability instance, they find a valid label placement whose labels are at least half as large as the optimal solution. That is, the approximation ratio of their algorithm is at most two. Similarly, if each label is rectangular and must be placed in such a way that the point it labels is somewhere along its bottom edge, then using 2-satisfiability to find the largest label size for which there is a solution in which each label has the point on a bottom corner leads to an approximation ratio of at most two.

Similar applications of 2-satisfiability have been made for other geometric placement problems. In graph drawing, if the vertex locations are fixed and each edge must be drawn as a circular arc with one of two possible locations (for instance as an arc diagram), then the problem of choosing which arc to use for each edge in order to avoid crossings is a 2-satisfiability problem with a variable for each edge and a constraint for each pair of placements that would lead to a crossing. However, in this case it is possible to speed up the solution, compared to an algorithm that builds and then searches an explicit representation of the implication graph, by searching the graph implicitly. In VLSI integrated circuit design, if a collection of modules must be connected by wires that can each bend at most once, then again there are two possible routes for the wires, and the problem of choosing which of these two routes to use, in such a way that all wires can be routed in a single layer of the circuit, can be solved as a 2-satisfiability instance.

consider another VLSI design problem: the question of whether or not to mirror-reverse each module in a circuit design. This mirror reversal leaves the module's operations unchanged, but it changes the order of the points at which the input and output signals of the module connect to it, possibly changing how well the module fits into the rest of the design. Boros et al. consider a simplified version of the problem in which the modules have already been placed along a single linear channel, in which the wires between modules must be routed, and there is a fixed bound on the density of the channel (the maximum number of signals that must pass through any cross-section of the channel). They observe that this version of the problem may be solved as a 2-satisfiability instance, in which the constraints relate the orientations of pairs of modules that are directly across the channel from each other. As a consequence, the optimal density may also be calculated efficiently, by performing a binary search in which each step involves the solution of a 2-satisfiability instance.

Data clustering
One way of clustering a set of data points in a metric space into two clusters is to choose the clusters in such a way as to minimize the sum of the diameters of the clusters, where the diameter of any single cluster is the largest distance between any two of its points. This is preferable to minimizing the maximum cluster size, which may lead to very similar points being assigned to different clusters. If the target diameters of the two clusters are known, a clustering that achieves those targets may be found by solving a 2-satisfiability instance. The instance has one variable per point, indicating whether that point belongs to the first cluster or the second cluster. Whenever any two points are too far apart from each other for both to belong to the same cluster, a clause is added to the instance that prevents this assignment.

The same method also can be used as a subroutine when the individual cluster diameters are unknown. To test whether a given sum of diameters can be achieved without knowing the individual cluster diameters, one may try all maximal pairs of target diameters that add up to at most the given sum, representing each pair of diameters as a 2-satisfiability instance and using a 2-satisfiability algorithm to determine whether that pair can be realized by a clustering. To find the optimal sum of diameters one may perform a binary search in which each step is a feasibility test of this type. The same approach also works to find clusterings that optimize other combinations than sums of the cluster diameters, and that use arbitrary dissimilarity numbers (rather than distances in a metric space) to measure the size of a cluster. The time bound for this algorithm is dominated by the time to solve a sequence of 2-satisfiability instances that are closely related to each other, and shows how to solve these related instances more quickly than if they were solved independently from each other, leading to a total time bound of $O(n^{3})$ for the sum-of-diameters clustering problem.

Scheduling
consider a model of classroom scheduling in which a set of n teachers must be scheduled to teach each of m cohorts of students. The number of hours per week that teacher $$i$$ spends with cohort $$j$$ is described by entry $$R_{ij}$$ of a matrix $$R$$ given as input to the problem, and each teacher also has a set of hours during which he or she is available to be scheduled. As they show, the problem is NP-complete, even when each teacher has at most three available hours, but it can be solved as an instance of 2-satisfiability when each teacher only has two available hours. (Teachers with only a single available hour may easily be eliminated from the problem.) In this problem, each variable $$v_{ij}$$ corresponds to an hour that teacher $$i$$ must spend with cohort $$j$$, the assignment to the variable specifies whether that hour is the first or the second of the teacher's available hours, and there is a 2-satisfiability clause preventing any conflict of either of two types: two cohorts assigned to a teacher at the same time as each other, or one cohort assigned to two teachers at the same time.

apply 2-satisfiability to a problem of sports scheduling, in which the pairings of a round-robin tournament have already been chosen and the games must be assigned to the teams' stadiums. In this problem, it is desirable to alternate home and away games to the extent possible, avoiding "breaks" in which a team plays two home games in a row or two away games in a row. At most two teams can avoid breaks entirely, alternating between home and away games; no other team can have the same home-away schedule as these two, because then it would be unable to play the team with which it had the same schedule. Therefore, an optimal schedule has two breakless teams and a single break for every other team. Once one of the breakless teams is chosen, one can set up a 2-satisfiability problem in which each variable represents the home-away assignment for a single team in a single game, and the constraints enforce the properties that any two teams have a consistent assignment for their games, that each team have at most one break before and at most one break after the game with the breakless team, and that no team has two breaks. Therefore, testing whether a schedule admits a solution with the optimal number of breaks can be done by solving a linear number of 2-satisfiability problems, one for each choice of the breakless team. A similar technique also allows finding schedules in which every team has a single break, and maximizing rather than minimizing the number of breaks (to reduce the total mileage traveled by the teams).

Discrete tomography
Tomography is the process of recovering shapes from their cross-sections. In discrete tomography, a simplified version of the problem that has been frequently studied, the shape to be recovered is a polyomino (a subset of the squares in the two-dimensional square lattice), and the cross-sections provide aggregate information about the sets of squares in individual rows and columns of the lattice. For instance, in the popular nonogram puzzles, also known as paint by numbers or griddlers, the set of squares to be determined represents the dark pixels in a binary image, and the input given to the puzzle solver tells him or her how many consecutive blocks of dark pixels to include in each row or column of the image, and how long each of those blocks should be. In other forms of digital tomography, even less information about each row or column is given: only the total number of squares, rather than the number and length of the blocks of squares. An equivalent version of the problem is that we must recover a given 0-1 matrix given only the sums of the values in each row and in each column of the matrix.

Although there exist polynomial time algorithms to find a matrix having given row and column sums, the solution may be far from unique: any submatrix in the form of a 2 × 2 identity matrix can be complemented without affecting the correctness of the solution. Therefore, researchers have searched for constraints on the shape to be reconstructed that can be used to restrict the space of solutions. For instance, one might assume that the shape is connected; however, testing whether there exists a connected solution is NP-complete. An even more constrained version that is easier to solve is that the shape is orthogonally convex: having a single contiguous block of squares in each row and column. Improving several previous solutions, showed how to reconstruct connected orthogonally convex shapes efficiently, using 2-SAT. The idea of their solution is to guess the indexes of rows containing the leftmost and rightmost cells of the shape to be reconstructed, and then to set up a 2-satisfiability problem that tests whether there exists a shape consistent with these guesses and with the given row and column sums. They use four 2-satisfiability variables for each square that might be part of the given shape, one to indicate whether it belongs to each of four possible "corner regions" of the shape, and they use constraints that force these regions to be disjoint, to have the desired shapes, to form an overall shape with contiguous rows and columns, and to have the desired row and column sums. Their algorithm takes time $O(m^{3}n)$ where $m$ is the smaller of the two dimensions of the input shape and $n$ is the larger of the two dimensions. The same method was later extended to orthogonally convex shapes that might be connected only diagonally instead of requiring orthogonal connectivity.

A part of a solver for full nonogram puzzles, used 2-satisfiability to combine information obtained from several other heuristics. Given a partial solution to the puzzle, they use dynamic programming within each row or column to determine whether the constraints of that row or column force any of its squares to be white or black, and whether any two squares in the same row or column can be connected by an implication relation. They also transform the nonogram into a digital tomography problem by replacing the sequence of block lengths in each row and column by its sum, and use a maximum flow formulation to determine whether this digital tomography problem combining all of the rows and columns has any squares whose state can be determined or pairs of squares that can be connected by an implication relation. If either of these two heuristics determines the value of one of the squares, it is included in the partial solution and the same calculations are repeated. However, if both heuristics fail to set any squares, the implications found by both of them are combined into a 2-satisfiability problem and a 2-satisfiability solver is used to find squares whose value is fixed by the problem, after which the procedure is again repeated. This procedure may or may not succeed in finding a solution, but it is guaranteed to run in polynomial time. Batenburg and Kosters report that, although most newspaper puzzles do not need its full power, both this procedure and a more powerful but slower procedure which combines this 2-satisfiability approach with the limited backtracking of are significantly more effective than the dynamic programming and flow heuristics without 2-satisfiability when applied to more difficult randomly generated nonograms.

Renamable Horn satisfiability
Next to 2-satisfiability, the other major subclass of satisfiability problems that can be solved in polynomial time is Horn-satisfiability. In this class of satisfiability problems, the input is again a formula in conjunctive normal form. It can have arbitrarily many literals per clause but at most one positive literal. found a generalization of this class, renamable Horn satisfiability, that can still be solved in polynomial time by means of an auxiliary 2-satisfiability instance. A formula is renamable Horn when it is possible to put it into Horn form by replacing some variables by their negations. To do so, Lewis sets up a 2-satisfiability instance with one variable for each variable of the renamable Horn instance, where the 2-satisfiability variables indicate whether or not to negate the corresponding renamable Horn variables. In order to produce a Horn instance, no two variables that appear in the same clause of the renamable Horn instance should appear positively in that clause; this constraint on a pair of variables is a 2-satisfiability constraint. By finding a satisfying assignment to the resulting 2-satisfiability instance, Lewis shows how to turn any renamable Horn instance into a Horn instance in polynomial time. By breaking up long clauses into multiple smaller clauses, and applying a linear-time 2-satisfiability algorithm, it is possible to reduce this to linear time.

Other applications
2-satisfiability has also been applied to problems of recognizing undirected graphs that can be partitioned into an independent set and a small number of complete bipartite subgraphs, inferring business relationships among autonomous subsystems of the internet, and reconstruction of evolutionary trees.

NL-completeness
A nondeterministic algorithm for determining whether a 2-satisfiability instance is not satisfiable, using only a logarithmic amount of writable memory, is easy to describe: simply choose (nondeterministically) a variable v and search (nondeterministically) for a chain of implications leading from v to its negation and then back to v. If such a chain is found, the instance cannot be satisfiable. By the Immerman–Szelepcsényi theorem, it is also possible in nondeterministic logspace to verify that a satisfiable 2-satisfiability instance is satisfiable.

2-satisfiability is NL-complete, meaning that it is one of the "hardest" or "most expressive" problems in the complexity class NL of problems solvable nondeterministically in logarithmic space. Completeness here means that a deterministic Turing machine using only logarithmic space can transform any other problem in NL into an equivalent 2-satisfiability problem. Analogously to similar results for the more well-known complexity class NP, this transformation together with the Immerman–Szelepcsényi theorem allow any problem in NL to be represented as a second order logic formula with a single existentially quantified predicate with clauses limited to length 2. Such formulae are known as SO-Krom. Similarly, the implicative normal form can be expressed in first order logic with the addition of an operator for transitive closure.

The set of all solutions
The set of all solutions to a 2-satisfiability instance has the structure of a median graph, in which an edge corresponds to the operation of flipping the values of a set of variables that are all constrained to be equal or unequal to each other. In particular, by following edges in this way one can get from any solution to any other solution. Conversely, any median graph can be represented as the set of solutions to a 2-satisfiability instance in this way. The median of any three solutions is formed by setting each variable to the value it holds in the majority of the three solutions. This median always forms another solution to the instance.

describes an algorithm for efficiently listing all solutions to a given 2-satisfiability instance, and for solving several related problems. There also exist algorithms for finding two satisfying assignments that have the maximal Hamming distance from each other.

Counting the number of satisfying assignments
#2SAT is the problem of counting the number of satisfying assignments to a given 2-CNF formula. This counting problem is #P-complete, which implies that it is not solvable in polynomial time unless P = NP. Moreover, there is no fully polynomial randomized approximation scheme for #2SAT unless NP = RP and this even holds when the input is restricted to monotone 2-CNF formulas, i.e., 2-CNF formulas in which each literal is a positive occurrence of a variable.

The fastest known algorithm for computing the exact number of satisfying assignments to a 2SAT formula runs in time $$O(1.2377^n)$$.

Random 2-satisfiability instances
One can form a 2-satisfiability instance at random, for a given number n of variables and m of clauses, by choosing each clause uniformly at random from the set of all possible two-variable clauses. When m is small relative to n, such an instance will likely be satisfiable, but larger values of m have smaller probabilities of being satisfiable. More precisely, if m/n is fixed as a constant α ≠ 1, the probability of satisfiability tends to a limit as n goes to infinity: if α < 1, the limit is one, while if α > 1, the limit is zero. Thus, the problem exhibits a phase transition at α = 1.

Maximum-2-satisfiability
In the maximum-2-satisfiability problem (MAX-2-SAT), the input is a formula in conjunctive normal form with two literals per clause, and the task is to determine the maximum number of clauses that can be simultaneously satisfied by an assignment. Like the more general maximum satisfiability problem, MAX-2-SAT is NP-hard. The proof is by reduction from 3SAT.

By formulating MAX-2-SAT as a problem of finding a cut (that is, a partition of the vertices into two subsets) maximizing the number of edges that have one endpoint in the first subset and one endpoint in the second, in a graph related to the implication graph, and applying semidefinite programming methods to this cut problem, it is possible to find in polynomial time an approximate solution that satisfies at least 0.940... times the optimal number of clauses. A balanced MAX 2-SAT instance is an instance of MAX 2-SAT where every variable appears positively and negatively with equal weight. For this problem, Austrin has improved the approximation ratio to $$\min \left\{(3 - \cos \theta)^{-1} (2 + (2/\pi)\theta) \,:\, \pi/2 \leq \theta \leq \pi \right\} = 0.943...$$.

If the unique games conjecture is true, then it is impossible to approximate MAX 2-SAT, balanced or not, with an approximation constant better than 0.943... in polynomial time. Under the weaker assumption that P ≠ NP, the problem is only known to be inapproximable within a constant better than 21/22 = 0.95454...

Various authors have also explored exponential worst-case time bounds for exact solution of MAX-2-SAT instances.

Weighted-2-satisfiability
In the weighted 2-satisfiability problem (W2SAT), the input is an $$n$$-variable 2SAT instance and an integer $k$, and the problem is to decide whether there exists a satisfying assignment in which exactly $k$ of the variables are true.

The W2SAT problem includes as a special case the vertex cover problem, of finding a set of $k$ vertices that together touch all the edges of a given undirected graph. For any given instance of the vertex cover problem, one can construct an equivalent W2SAT problem with a variable for each vertex of a graph. Each edge $uv$ of the graph may be represented by a 2SAT clause $u ∨ v$ that can be satisfied only by including either $u$ or $v$ among the true variables of the solution. Then the satisfying instances of the resulting 2SAT formula encode solutions to the vertex cover problem, and there is a satisfying assignment with $k$ true variables if and only if there is a vertex cover with $k$ vertices. Therefore, like vertex cover, W2SAT is NP-complete.

Moreover, in parameterized complexity W2SAT provides a natural W[1]-complete problem, which implies that W2SAT is not fixed-parameter tractable unless this holds for all problems in W[1]. That is, it is unlikely that there exists an algorithm for W2SAT whose running time takes the form $f(k)·n^{O(1)}$. Even more strongly, W2SAT cannot be solved in time $n^{o(k)}$ unless the exponential time hypothesis fails.

Quantified Boolean formulae
As well as finding the first polynomial-time algorithm for 2-satisfiability, also formulated the problem of evaluating fully quantified Boolean formulae in which the formula being quantified is a 2-CNF formula. The 2-satisfiability problem is the special case of this quantified 2-CNF problem, in which all quantifiers are existential. Krom also developed an effective decision procedure for these formulae. showed that it can be solved in linear time, by an extension of their technique of strongly connected components and topological ordering.

Many-valued logics
The 2-satisfiability problem can also be asked for propositional many-valued logics. The algorithms are not usually linear, and for some logics the problem is even NP-complete. See for surveys.

title: 2-satisfiability


text:
Alvin Ailey

Alvin Ailey Jr. (January 5, 1931 – December 1, 1989) was an American dancer, director, choreographer, and activist who founded the Alvin Ailey American Dance Theater (AAADT). He created AAADT and its affiliated Alvin Ailey American Dance Center (later Ailey School) as havens for nurturing Black artists and expressing the universality of the African-American experience through dance.

Ailey's work fused theater, modern dance, ballet, and jazz with Black vernacular, creating hope-fueled choreography that continues to spread global awareness of Black life in America. Ailey's choreographic masterpiece Revelations is recognized as one of the most popular and most performed ballets in the world.

On July 15, 2008, the United States Congress passed a resolution designating AAADT a "vital American cultural ambassador to the World." That same year, in recognition of AAADT's 50th anniversary, then Mayor Michael Bloomberg declared December 4 "Alvin Ailey Day" in New York City, while then-Governor David Paterson honored the organization on behalf of New York State.

Early life and education
Ailey was born to Alvin Ailey and Lula Elizabeth Cliff in Rogers, Texas, in his maternal grandfather's home at the height of the Great Depression. As a child in the violently racist and segregated south, during his youth Ailey was barred from interacting with mainstream society. When he was five, Ailey's mother was raped by four white men (one likely an employer), and Ailey recalled seeing members of the Ku Klux Klan as a child.

The elder Alvin Ailey abandoned the young Alvin and Lula shortly after Alvin was born, leaving Lula to work in cotton fields and as a domestic in white homes — the only employment available to her. By the time Ailey was five, he joined his mother picking cotton. After a white man raped Lula in 1936, Ailey began to fear white men. As an escape, Ailey found refuge in the church, sneaking out at night to watch adults dance, and in writing a journal, a practice that he maintained his entire life. Even this could not shield him from a childhood spent moving from town to town as his mother sought employment, being abandoned with relatives whenever she took off on her own.

Looking for greater job prospects, Ailey's mother departed for Los Angeles in 1941. He arrived a year later, enrolling at George Washington Carver Junior High School, and then graduating into Thomas Jefferson High School. He was able to explore the arts in high school, singing in glee club and writing poetry. He also took gymnastics. He frequently attended Lincoln Theatre and the Orpheum Theatre, where he was able to see a variety of African American performers, including Pearl Bailey, Fletcher Henderson, Billie Holiday, Lena Horne, Pigmeat Markham, Count Basie, and Duke Ellington. In 1946 he had his first experience with concert dance, awakening an until then unknown spark of joy within him, when he saw Ballet Russe de Monte Carlo on a school trip and Katherine Dunham Dance Company's "Tropical Review" on solitary trips to the Los Angeles Philharmonic Auditorium.

Also in high school, Ailey discovered his homosexuality, which added another layer of difference and isolation to his already racially segregated experience. Thus, "like many young gay men eager to corral the sensual impulses of the body, he turned to dance study." He briefly studied tap, followed by exploring "primitive dance" as taught by Dunham dancer Thelma Robinson. Neither of these styles were right for Ailey, possibly due to the physical location and old-fashioned sensibility of the lessons. Therefore, he did not become serious about dance until 1949 when his classmate and friend Carmen De Lavallade dragged him to the Melrose Avenue studio of Lester Horton and he began exploring modern dance.

Ailey studied a wide range of dance styles and techniques — from ballet to Native American inspired movement studies — at Horton's school, which was one of the first racially integrated dance schools in the United States. Though Horton became his mentor, Ailey did not commit to dancing full-time, recognizing the lack of opportunities for black male dancers. Instead, he pursued academic courses, studying romance languages and writing at UCLA (1949), Los Angeles City College (1950–1951), and San Francisco State (1952). During this time, he sporadically returned to Horton to work between courses. Living in San Francisco, he met Maya Angelou, then known as Marguerite Johnson, with whom he formed a nightclub act called "Al and Rita." Eventually, he returned to study dance with Horton in Los Angeles.

Horton Dance Company
Ailey joined Horton's dance company in 1953. While there, he took daily technique classes, studied art and music, and taught children's classes. In 1953, he made his debut in Horton's Revue Le Bal Caribe. In a workshop the summer of 1953, Ailey created his first dance composition, Afternoon Blues. This work was a three minute solo blues adaptation of L’Aprés Midi d’un Faune, which he had seen performed by the Ballet Russe de Monte Carlo. In this piece, Ailey played the eponymous Faun to a selection from On the Town (musical).

Horton died suddenly November 1953 from a heart attack, leaving the company without leadership. In order to complete the organization's pressing professional engagements, and because no one else was willing to, Ailey took over as artistic director and choreographer. In particular, Horton's company was committed to performing at Jacob's Pillow in the summer of 1954. Ailey worked collaboratively with the Horton company dancers and choreographed based on them, gaining the support of the company's dancers who had much more experience than Ailey. These works included According to St. Francis (4 June 1954), a tribute to Horton as a "kind of allusion to Lester's life" featuring James Truitte. He also choreographed and directed Morning Mourning (4 June 1954), a piece based on the work of Tennessee Williams featuring de Lavallade and set to an original score by Gertrude Rivers Robinson. As Horton had done, Ailey designed the sets for Morning Mourning and collaborated on the lighting. That summer, Ailey also made his first large group piece, Creation of the World (13 July 1954), set to a score by Darius Milhaud. Under Ailey, the Horton company had commercial engagements on television programs Party at Ciro's, The Red Skelton Show, and the Jack Benny show. Ailey and de Lavallade also performed in a segment of Carmen Jones.

Early New York Career
In December, 1954 De Lavallade and Ailey were recruited by Herbert Ross (who had coreographed Carmen Jones) to join the Broadway show, House of Flowers. Ross had been hired to replace George Balanchine as the show's choreographer and he wanted to use the pair, who had become known as a famous dance team in Los Angeles, as featured dancers. The show's book was written and adapted by Truman Capote from one of his novellas with music from Harold Arlen and starred Pearl Bailey and Diahann Carroll.

Ailey and De Lavallade met Geoffrey Holder, who performed alongside them in the chorus, during the production. Holder married De Lavallade and became a life-long artistic collaborator with Ailey. After House of Flowers closed, Ailey appeared in Harry Belafonte's touring revue Sing, Man, Sing with Mary Hinkson as his dance partner, and the 1957 Broadway musical Jamaica, which starred Lena Horne and Ricardo Montalbán. Throughout the late 1950s, Ailey continued to study dance technique sporadically, learning with the New Dance Group's Hanya Holm, Anna Sokolow, Charles Weidman, and Karel Shook. Drawn to dance, but unable to find a choreographer whose work fulfilled him and wanting to continue the work he had begun at the Horton school, Ailey started gathering dancers to perform his own unique vision of dance.

The Early Alvin Ailey Dance Theater
In 1958 Ailey founded the Alvin Ailey American Dance Theater to present his vision of honoring Black culture through dance. The company had its debut at the 92nd Street YM-YWHA on March 30, 1958 in a concert shared with choreographer Ernest Parham, with headlining guest artist Talley Beatty. The performance included Ailey's first masterpiece, Blues Suite, which drew from Ailey's Texas childhood and House of Flowers, following men and women as they caroused and cavorted over the course of an evening while blues music played in the background until church bells began to ring, signaling a return to mundane life. Ailey danced in the other two premieres at this performance, Redonda and Ode and Homage. Redonda, which was later retitled Cinco Latinos, brought together five short pieces described as "Latin Theme" in a work similar to Horton's. Ode and Homage, set to a score by Peggy Glanville-Hicks, was a "dance of faith, respectfully dedicated to the memory of Lester Horton."

Following the success of his first concert, Ailey continued choreographing for a shifting roster of dancers who were available for dances at the 92nd Street YM-YWHA, working with designers Normand Maxon, Ves Harper, and Nicola Cernovich. These works included the integrated Ariette Oubliée (21 December 1958, a choreographic fantasy pantomime set to Debussy's similarly named song cycle and featuring Don Price and de Lavallade. He also choreographed for other companies in collaborations, such as a version of Miss Julie, "Mistress and Manservant," to a score by Ravel for the Shirley Broughton Dance Company.

On January 31, 1960, the AADT premiered several new works at the 92nd Street YM-YWHA. These included Sonera, Ailey's first attempt at choreographing on point. Ailey also reworked Creation of the World for this performance as a duet for himself and Matt Turney of the Martha Graham Dance Company, which received great acclaim. He also premiered his most popular and critically acclaimed work, Revelations. In creating Revelations, Ailey drew upon his "blood memories" of growing up in Texas surrounded by Black people, the church, spirituals, and the blues. The ballet charts the full range of feelings, from the majestic "I Been ’Buked" to the rapturous "Wade in the Water," closing with the electrifying finale, "Rocka My Soul in the Bosom of Abraham." In 1960, Edele Holz offered Ailey rehearsal space at what would become the Clark Center for the Performing Arts. Shortly after the center opened in October of that year, AADT had its first concert. This concert included a November 27, 1960 premiered Knoxville: Summer of 1915, set to music by Samuel Barber and based on A Death in the Family and Three for Now, set to music by Jimmy Giuffre and John Lewis (pianist), as well as Horton's The Beloved and John Butler's Portrait of Billie. The next year, he premiered Hermit Songs (10 December 1961). Originally conceived as a group work, it premiered as a solo for Ailey performed to Leontyne Price's recording of Samuel Barber's Hermit Songs. Hermit Songs, which is based on a loose narrative of a monk's privilege and penance, remained in the AADT's repertoire through 1991.

Ailey's work during this time was different from many other modern dance choreographers of the time. By keeping a focus on narrative, he was able to draw an audience from outside New York City and the avant garde.

Work with the US State Department and Later Work
In the fall of 1961, the US State Department invited the AADT (under the banner of the Lavallade-Ailey American Dance Company) to tour Southeast Asia and Australia as a part of President Kennedy's Special International Program for Cultural Presentations. This led Ailey to assemble a repertory that the State Department would find appropriate, including a new dance, Been Here and Gone, a suite of folk songs and children's games based on Donald McKayle's Games (which Ailey had performed in 1956) and his own memories of growing up in Texas. He also assembled a company of ten dancers and four musicians that could travel the world. This tour began on 3 February in Sydney, Australia, and ended on 12 May 1962 in Seoul, South Korea, performing sixty times in thirteen weeks. As necessary, Ailey reworked material to fit the shifting roster of collaborators. Many of the works, including Roots of the Blues and Revelations were specifically reworked to feature the headlining de Lavallade. The tour had followups at the World Festival of Negro Arts in Dakar, Senegal in 1966, East & West Africa in 1967, and the Edinburgh Festival in 1968. Biographer Thomas DeFrantz notes how the Ailey company's status as "the sole exponent of an emerging standard of African American concert dance" allowed the U.S. government to covertly mold the "signature style of Afro-American concert dance." He also notes that State Department propaganda aided in promoting the international celebrity of the AADT.

The relationship with the State Department did not go well and ended after a few years. Ailey struggled with the state department tours, which insisted on marketing the company as an "ethnic" company rather than a modern dance company, and were closely supervised by the FBI - the latter referred to Ailey's homosexuality as "lewd and criminal tendencies" and threatened his company with bankruptcy if he showed any signs of effeminate or homosexual behavior while on tour.

Despite their work with the State Department, the company was able to book only a few performances per season in America. For a major concert at the Brooklyn Academy of Music on 28 April 1963, Ailey reworked movements of Revelations into "Reflections in D," (set to music by Duke Ellington) which, combined with "Suspensions," and "Gillespiana" made the latest version of Three for Now. Ailey also premiered Labyrinth, telling the story of Theseus and the Minotaur, which was later reborn as Ariadne.

Also in 1963, Ailey began his professional relationship with Duke Ellington. Ellington invited Ailey to perform in My People (First Negro Centennial), a travelogue history in observance of the centennial of the Emancipation Proclamation. For the August 19 performance, Ailey coreographed three pieces, “The Blues Ain't,” "Light," and "My Mother My Father." While working with Ellington, Ailey and his company were invited to the International Music Festival in Rio de Janeiro. For this performance, feeling the occasion required a new work, Ailey premiered Rivers, Streams, and Doors.

In August 1964, Ailey choreographed a dance, The Twelve Gates, in honor of Ruth St. Denis and Ted Shawn's golden anniversary. This performance, featuring Truitte and de Lavallade, and with costumes by Holder, was performed for a single week at Jacob's Pillow. In the fall of 1964, Ailey added "American" to his company's name during a three month European tour. In 1965, following physical tensions and negative reviews at the Florentine Festival, Ailey retired from his career as a dancer. Ailey paused choreography until receiving a lucrative commission by the Swedish television for Riedaiglia, which was danced to a commissioned score by Georg Riedel and relied heavily on television director Lars Egler's direction. This dance immediately won the television award the Grand Prix Italia, and was later broadcast in the United States on Ambassadors of Dance.

In the summer of 1968, Ailey received a Guggenheim Fellowship. With these funds, he created his first work set to pop music, choreographing Quintet to six songs from Eli and the Thirteenth Confession. This work debuted at the 1968 Edinburgh Festival, and premiered in New York at the Billy Rose Theatre as a part of AAADT's first Broadway season. The next year, he created Diversion No.1, including dances to Scarborough Fair and Oh Happy Day for a program shared with The 5th Dimension. This work, created to attract audiences to the AAADT's UCLA season, was one of Ailey's most commercial pieces.

In a twelve-day residency at Connecticut College in 1968, Ailey created Masekela Langage, a piece set in South Africa. This work directly addresses racial politics with the intention of drawing a parallel between the Apartheid and the shooting to death of Fred Hampton. This politicism was uncommon for Ailey's work. The piece received immediate acclaim, and is regularly revived by the AAADT.

After a successful week-long engagement at the Billy Rose Theatre, the company was invited to become the resident company at Brooklyn Academy of Music in 1969. This residency included a revival of Revelations. While working with BAM, he sponsored free classes for children and young adults "geared to channel formidable youth rage into art." Ailey was dissatisfied with the residency due to cramped quarters and BAM directer Harvey Lichtenstein's racialized business tactics.

In 1970, with few bookings on the radar — and on the eve of a tour to Russia as part of a cultural exchange agreement — Ailey announced at a press conference that he was closing the company. In response, the State Department sponsored an Ailey tour of North Africa to tide things over. That August, the company toured to Russia, where it was ecstatically received. The AAADT became the first American modern dance company to perform in the Soviet Union. Their performances were broadcast on Moscow television and seen by over 22 million viewers. On closing night, because the Russian audiences would not stop applauding, the company gave over 30 curtain calls. Returning home with news of this triumph, the company performed a two-week engagement at the ANTA Theater. At this performance, he premiered Flowers, set to music by Blind Faith, Pink Floyd, and Janis Joplin with Big Brother and the Holding Company. Flowers, which featured Lynn Seymour, depicted the death of a rock star caused by drug addiction, inspired by Joplin's death on October 3, 1970 and dedicated to "a slew of rockers making youth-oriented music." By the end of the January 1971 performance, the entire run was sold out. After 13 years, Alvin Ailey American Dance Theatre was a monumental success.

In August 1972, the company was briefly renamed Alvin Ailey City Center Dance Theater and became a resident company of New York City Center. In September of that year, Ailey created Shaken Angels, another rock-based piece. This piece, set to recorded music by Alice Cooper, Pink Floyd, and Bill Withers, featured Dennis Wayne and Bonnie Mathis in story about a couple "cornered into a relationship of violence and need, smoking pot and mainlining heroin. The work spilled into the audience as Wayne chased Mathis through the aisles, dragging her onto the stage and striking her with a needle.

In 1973, the AAADT headlined the First National Congress on Blacks in Dance, though Ailey sat out of conversaitions on how to advance the public perception and financial profiles of black dance companies.

In 1975, Ailey restaged Revelations for nineteen dancers for a staging at the New York State Theater from August 12 to 24.

While Ailey choreographed more than 100 ballets for his dancers, he insisted that the company perform pieces by other choreographers rather than stand as a singular vehicle for his voice.

Though AAADT was formed to celebrate African American culture and to provide performances for black dancers, who were frequently denied opportunities due to racist mores of the time, Ailey proudly employed artists based solely on artistic talent and integrity, regardless of their background. In addition to his work as artistic director and choreographer with AADT, Ailey also choreographed ballets for other companies including American Ballet Theatre, Joffrey Ballet, Royal Danish Ballet, and The Metropolitan Opera. For American Ballet Theatre, he created The River (1970), one of several choreographies he set to the jazz music of Duke Ellington.

Commercial Work
Throughout his career, Ailey continued to pursue work as a commercial theater choreographer, re-staging Carmen Jones (August 1959) and Jamaica (1960) for Summer stock theater and staging dances for the theatrical review African Holiday (1960) and Dark Side of the Moon (May 1960). These commercial engagements remained segregated, with African American casts generally hired to entertain mostly white audiences. Ailey also studied acting with Stella Adler from 1960 to 1962, acting in non-dancing roles in dramatic plays including Call Me by My Rightful Name (January 1961) with costars Robert Duvall and Joan Hackett, and Tiger, Tiger Burning Bright, also starting Roscoe Lee Browne, Al Freeman Jr., Claudia McNeil, Diana Sands, and Cicely Tyson. These plays all constructed race as a societal force and "agent of division."

In 1964, at a direct request from Langston Hughes, Ailey directed Jerico-Jim Crow with William Hairston. His one attempt at Broadway choreography, La Strada (musical), opened and closed in one performance on December 14, 1969.

The Ailey School
In 1969, Ailey founded the Alvin Ailey American Dance Center with the famed Martha Graham Dance Company principal and choreographer Pearl Lang as his co-director of the school. Their aim was to provide access to arts and dance to under-resourced communities. They started off in Brooklyn with 125 students. A year later the school relocated to Manhattan behind the Lincoln Center complex. In 1984, Denise Jefferson assumed directorship. Under her leadership, the school developed a Bachelor of Fine Arts Program in partnership with Fordham University in 1998.

The school was renamed The Ailey School in 1999. Several years later, the school moved into The Joan Weill Center for Dance. Following Jefferson's death in 2010, Tracy Inman and Melanie Person assumed stewardship of the school as co-directors of the school. In 2012, after leading Ailey 2 for 38 years, Sylvia Waters retired. The second company's resident choreographer and associate director Troy Powell took over her role as artistic director. With the addition of the Elaine Wynn and Family Education Wing, the Ailey school is still growing and is now the largest place in New York City committed to training dancers.

From her joining in 1965, the dancer Judith Jamison served as Ailey's muse. In 1971 she premiered Cry, which he dedicated to his mother and black women everywhere. She took over as artistic director following his death in 1989.

Other important figures in the company include Sylvia Waters, who in 1974, after performing with the company for six year was asked by Ailey to lead The Alvin Ailey Repertory Ensemble — a junior company, known today as Ailey 2, that prepares leading students for professional dance careers - and Masazumi Chaya, who danced with the company for 15 years then became rehearsal director, and was appointed associate artistic director in 1991.

Personal life
Ailey was uncomfortable with the label "Black choreographer" and preferred being known simply as a choreographer, while also acknowledging to the Chicago Tribune in 1987, "Of course there is something black in my work: me and my 56 years." He was known to be private about his personal life.

Death
Ailey died from an AIDS-related illness on December 1, 1989, at the age of 58. He asked his doctor to announce that his death was caused by terminal blood dyscrasia in order to shield his mother from the stigma associated with HIV/AIDS.

On December 9, 1989, over 4,000 mourners attended his funeral at the Cathedral of St. John the Divine. The funeral, which lasted two hours, featured his friend Maya Angelou reading an oral interpretation of her poem "For Alvin Ailey," drumming by Max Roach, a reading of a statement from President George H. W. Bush, and eulogies by de Lavallade, Jamison, and New York City mayor David Dinkins. The funeral also included performances of Ailey's choreography on a makeshift stage constructed around his casket. These included Dudley Williams performing "Song for You," Donna Wood dancing an excerpt from "Cry," and excerpts from Revelations performed by Mari Kajiwara, John Parks, and members of his dance company.

Ailey was buried in Los Angeles.

Recognition and honors

 * 1968: Guggenheim Fellowship for Creative Arts, US & Canada
 * 1972: Princeton University's honorary Doctorate of Fine Arts
 * 1975: Dance Magazine citation
 * 1977: Spingarn Medal from the NAACP
 * 1979: Capezio Award
 * 1987: Samuel H. Scripps American Dance Festival Award
 * 1989: Kennedy Center Honors
 * 1992: Inducted into the National Museum of Dance and Hall of Fame
 * 2012: Ailey crater on Mercury named in his honor
 * 2012: Inducted into the Legacy Walk in 2012
 * 2014: Posthumously received the Presidential Medal of Freedom from President Barack Obama.
 * 2017: VH1 Trailblazer Honors
 * August 2019: Inducted in the Rainbow Honor Walk, a walk of fame in San Francisco's Castro neighborhood noting LGBTQ people who have "made significant contributions in their fields"
 * 2020: Figure-skating choreographer Rohene Ward and Olympic medallist Jason Brown co-choreographed a tribute to Ailey set to Nina Simone's version of "Sinnerman," which Brown competed in both the 2020–2021 and 2021–2022 seasons, including at the 2022 Winter Olympics.

After his death, Ailey’s personal papers were housed at the Black Archives of Mid-America in Kansas City, Missouri.

Documentary
In 2021, the documentary Ailey by director Jamila Wignot was released in the United States. Wignot first discovered the work of the Alvin Ailey American Dance Theater by attending a performance while she was a student at Wellesley College; in her documentary more than twenty years later, Alexandra Villarreal of The Guardian writes, "What emerges is a towering figure who won worldwide acclaim with art steeped in personal experience, yet was too afraid to openly share his full identity even in death."

Though Ailey's work has been met with popular and critical acclaim, there have been detractors of his theatrical style. Marcia Siegel accused the company of "selling soul," and of amplifying and transforming the emotivity characteristic of Martha Graham and his modern dance teachers into "metaphors of the American black experience" while creating a positive stereotype of "supremely physical, supremely sensitive beings" at the expense of genuineness."

Ailey responded to such criticism by stating, "The black pieces we do that come from blues, spirituals and gospels are part of what I am. They are as honest and truthful as we can make them. I'm interested in putting something on stage that will have a very wide appeal without being condescending; that will reach an audience and make it part of the dance; that will get everybody into the theater. If it's art and entertainment — thank God, that's what I want to be."

Associated people
In 1960, James Truitte joined the dance company, and later became an authority on Lester Horton's technique.

Choreography

 * Afternoon Blues, Horton Dance Company, summer 1953.
 * According to St. Francis, Horton Dance Company, 4 June 1954.
 * Morning Mourning, Horton Dance Company, 4 June 1954.
 * Creation of the World, Horton Dance Company, 4 June 1954.
 * Cinco Latinos (originally Redonda), Alvin Ailey Dance Theatre, Kaufmann Concert Hall, New York City, 30 March 1958.
 * Blues Suite (also see below), Alvin Ailey Dance Theatre, Kaufmann Concert Hall, 30 March 1958.
 * Ode and Homage, Alvin Ailey Dance Theatre, Kaufmann Concert Hall, 30 March 1958.
 * Ariette Oubliée, Alvin Ailey Dance Theatre, 21 December 1958.
 * "Mistress and Manservant," Shirley Broughton Dance Company, 1 February 1959.
 * Sonera, Alvin Ailey Dance Theatre, 31 January 1960.
 * Revelations, Alvin Ailey Dance Theatre, Kaufmann Concert Hall, 31 January 1960
 * Three for Now, Alvin Ailey Dance Theatre, Clark Center, New York City, 27 November 1960.
 * Knoxville: Summer of 1915, Alvin Ailey Dance Theatre, Clark Center, 27 November 1960.
 * Three for Now, Alvin Ailey Dance Theatre, Clark Center, 27 November 1960.
 * (With Carmen De Lavallade) Roots of the Blues, Lewisohn Stadium, New York City, 1961.
 * Two for Now, Alvin Ailey Dance Theatre, 26 January 1962.
 * Been Here and Gone, Alvin Ailey Dance Theatre, 26 January 1962.
 * Hermit Songs, Alvin Ailey Dance Theatre, Library of Congress, Washington, D.C., 1963.
 * Three for Now, Alvin Ailey Dance Theatre, Brooklyn Academy of Music, 28 April 1963.
 * Labyrinth, Alvin Ailey Dance Theatre, Brooklyn Academy of Music, 28 April 1963.
 * "The Blues Ain't," Alvin Ailey Dance Theatre, My People (First Negro Centennial), 19 August 1963.
 * "Light," Alvin Ailey American Dance Theatre, My People (First Negro Centennial), 19 August 1963.
 * "My Mother, My Father," Alvin Ailey Dance Theatre, My People (First Negro Centennial), 19 August 1963.
 * Rivers, Streams, Doors, Alvin Ailey Dance Theatre, International Music Festival in Rio de Janeiro, 6 September 1963.
 * Ariadne, Harkness Ballet, Opera Comique, Paris, 1965.
 * Riedaiglia, Alvin Ailey American Dance Theatre, Sweden, 1967.
 * Macumba, Harkness Ballet, Gran Teatro del Liceo, Barcelona, Spain,1966, then produced as Yemanja, Chicago Opera House, 1967.
 * Quintet, Alvin Ailey American Dance Theatre, Church Hill Theatre, Edinburgh Festival, Scotland, 1968, then Billy Rose Theatre, New York City, 1969.
 * Diversion No. 1, Alvin Ailey American Dance Theatre, Greek Theatre (Los Angeles), 14 July 1969.
 * Masekela Langage, Alvin Ailey American Dance Theatre, American Dance Festival, New London, Connecticut, 1969, then Brooklyn Academy of Music, New York City, 1969.
 * Streams, Alvin Ailey American Dance Theatre, Brooklyn Academy of Music, 1970.
 * Gymnopedies, Alvin Ailey American Dance Theatre, Brooklyn Academy of Music, 23 August 1970.
 * The River, American Ballet Theatre, New York State Theater, 1970.
 * Flowers, Alvin Ailey American Dance Theatre, ANTA Theatre, 1971.
 * Myth, Alvin Ailey American Dance Theatre, New York City Center, 1971.
 * Choral Dances, Alvin Ailey American Dance Theatre, New York City Center, 1971.
 * Cry, solo created for Judith Jamison, Alvin Ailey American Dance Theatre, New York City Center, 1971.
 * Mingus Dances, Robert Joffrey Company, New York City Center, 1971.
 * Mary Lou's Mass, Alvin Ailey American Dance Theatre, New York City Center, 1971.
 * Archipelago, Festival of Contemporary Music at Royan, France, 18 January 1971.
 * Song for You, solo created for Dudley Williams, Alvin Ailey American Dance Theatre, New York City Center, 1972.
 * The Lark Ascending, Alvin Ailey American Dance Theatre, New York City Center, 1972.
 * Love Songs, Alvin Ailey City Center Dance Theater, New York City Center, 1972.
 * Shaken Angels, 10th New York Dance Festival, Delacorte Theatre, New York City, 1972.
 * Sea Change, American Ballet Theatre, Kennedy Center Opera House, Washington, D.C., 1972, then New York City Center, 1973.
 * Hidden Rites, Alvin Ailey City Center Dance Theater, New York City Center, 1973.
 * The Mooche, 1975,
 * Night Creature, 1975,
 * Pas de "Duke", 1976,
 * Memoria, 1979,
 * Phases, 1980
 * Landscape, 1981.
 * Survivors, 1986.

Acting and dancing

 * (Broadway debut) House of Flowers, Alvin Theatre, New York City, 1954 – Actor and dancer.
 * The Carefree Tree, 1955 – Actor and dancer.
 * Sing, Man, Sing, 1956 – Actor and dancer.
 * Show Boat, Marine Theatre, Jones Beach, New York, 1957 – Actor and dancer.
 * Jamaica, Imperial Theatre, New York City, 1957 – Actor and lead dance.
 * Call Me By My Rightful Name, One Sheridan Square Theatre, January 1961 – Paul.
 * Ding Dong Bell, Westport Country Playhouse, summer 1961 – Negro Political Leader.
 * Blackstone Boulevard, Talking to You, produced as double-bill in 2 by Saroyan, East End Theatre, New York City, 1961–62 – Blackstone Boulevard.
 * Tiger, Tiger, Burning Bright, Booth Theatre, December 1962 – Clarence Morris.

Stage choreography

 * Carmen Jones, Theatre in the Park, 1959.
 * Jamaica, Music Circus, Lambertville, New Jersey, 1959.
 * Dark of the Moon, Lenox Hill Playhouse, 1960.
 * (And director) African Holiday (musical), Apollo Theatre, New York City, 1960, then produced at Howard Theatre, Washington, D.C., 1960.
 * Feast of Ashes (ballet), Robert Joffrey Company, Teatro San Carlos, Lisbon, Portugal, 1962, then produced at New York City Center, 1971.
 * Antony and Cleopatra (opera), Metropolitan Opera House, Lincoln Center, New York City, 1966.
 * La Strada, first produced at Lunt-Fontanne Theatre, 1969.
 * Leonard Bernstein's Mass, Metropolitan Opera House, 1972, then John F. Kennedy delícia Center for the Performing Arts, Washington, D.C., and Philadelphia Academy of Music, both 1972.
 * Carmen, Metropolitan Opera, 1972.
 * Choreographed ballet, Lord Byron (opera; also see below), Juilliard School of Music, New York City, 1972.
 * Four Saint s in Three Acts, Piccolo Met, New York City, 1973.

Director

 * (With William Hairston) Jerico-Jim Crow, The Sanctuary, New York City, 1964, then Greenwich Mews Theatre, 1968.

Performer

 * Lydia Bailey, Specialty Dancer, 1952.
 * Carmen Jones (film), Dance Soloist, 1954.

Choreographer

 * American Ballet Theatre: A Close-Up in Time, choreographer, 1973.
 * "Ailey Celebrates Ellington", The CBS Festival of Lively Arts for Young People, choreographer, 1974.
 * The Turning Point (1977 film), choreographer for Miss Browne's Gala Solo, 1977.

Tributes to Ailey

 * A Tribute to Alvin Ailey, 1990.
 * "Dance in America: Beyond the Steps - Alvin Ailey American Dance Theater," Great Performances, 2006.
 * Ailey, 2021.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Alvin Ailey


text:
Talk:Horizon Air

Logo
Is the logo in the infobox current? I haven't seen it being used anywhere else.Mirza Ahmed (talk) 10:44, 30 June 2018 (UTC)

Yes it is, it isn’t on their planes but this is the actual logo for horizon air. Lufthansa122 (talk) 17:25, 22 February 2020 (UTC)

Eighth largest regional airline?
Is there a source for the claim Horizon was the "eighth largest regional airline in the US"? Eighth largest by what, passengers numbers or fleet size? Mirza Ahmed (talk) 13:10, 12 July 2018 (UTC)

2018 August 10 Incident
Twitter is aflame with rumours that a pilot made off with a Horizon a/c out of SeaTac. Watch for rapid edits and interest in the page.
 * Please wait until you can provide a Reliable Source - Wikipedia is not a Newspaper WP:NOTNEWS there is plenty of time to add the details of this developing story Andrewgprout (talk) 05:12, 11 August 2018 (UTC)

Please also note that Twitter is not really considered a reliable source WP:TWITTER Andrewgprout (talk) 05:15, 11 August 2018 (UTC)

To suck or to blow !
I have reverted this edit where  is maintaining rather asuredly that people can only be blown from an aircraft not sucked because the normal usage describing such is wrong in some overly technical sense. See this discussion on my talk page. There is a perfectly good commonplace definition of sucked in the Oxford dictionary that fits exactly how the word is used here. To quote "with object and adverbial of direction Draw in a specified direction by creating a vacuum". Andrewgprout (talk) 05:28, 13 September 2018 (UTC)

title: Talk:Horizon Air


text:
Walter Plinge

Walter Plinge is a pseudonym, used in British theatres since the 19th century on occasions when it is not possible or desirable to make an actor's real name known.

Name and usage
Walter Plinge is a pseudonym traditionally used in British theatres when a part has not been cast, an actor is playing two parts, or an actor does not want their name in the programme. The name has also been used in radio and television credits. Who's Who in the Theatre has this entry for the name: "'Plinge, Walter', actor; was discovered by the late H. O. Nicholson and first appeared with F. R. Benson's Shakespearean Company about 1898; was well-known in connection with minor parts in most of the plays of the extensive Benson repertory, and occasionally in other companies. Is related to 'Mr. Bart' and 'Mr. F. Anney' of the Benson Company, to 'George Spelvin' (USA) and 'A. N. Other' (Sport)."

In 1939 Alfred Wareing, a former member of Benson's company, wrote in The Stage that the real Walter Plinge had been the landlord of the public house in Wellington Street near the stage door of the Lyceum Theatre, London. Wareing recalled that Plinge was not entirely pleased at having his name used by Benson, particularly as the company already had other pseudonyms in use when needed. These included "R. Sherard" and "T. Ashman" – the latter used by among others Oscar Asche when doubling roles, although in Asche's case, according to Wareing, the false name "never deceived the knowing public". Another former Bensonian recalled the pseudonym "Hugh S. Hay" being used when the American actor Walter Hampden was in the company. The actor-manager Murray Carrington recalled that in the 1920s his company had featured not only Walter Plinge Jr. but also a female counterpart, Juliet Plinge.

The name Walter Plinge has been used occasionally in American theatre, where the more usual equivalent is "George Spelvin". Analogous pseudonyms – for writers rather than actors – are Alan Smithee in Hollywood and David Agnew at the BBC. From its earliest years the BBC has used "Walter Plinge" in its listings of acting roles, and "he" is the corporation's longest-serving broadcaster, having made his first broadcast in 1925, with subsequent appearances up to 2018.

Walter Plinge is also used as the name of a character in Terry Pratchett's novel Maskerade, which is a parody of opera and musical theatre. The character is an amalgam of two parts played by Michael Crawford: Frank Spencer and the Phantom of the Opera.

title: Walter Plinge


text:
User talk:XTaran~enwiki

Hi there. Welcome to Wikipedia! Thanks for all your work on computer topics. If you want, drop us a note at New user log to introduce yourself.

If you need editing help, visit How does one edit a page. For format questions, visit our manual of style. You can use the Show preview button before you save, to make sure your edits do what you intended.

You can sign your name on talk pages by using " " for your username and " ~ " for your username and a timestamp.

Some time when you're bored, you can read through our policies and guidelines. If you made any edits before you got an account, you might be interested in assigning those to your username.

If you have any other questions about the project then check out Help or add a question to the Village pump. You can also drop me a question on my talk page.

Happy editing, Isomorphic 20:03, 1 Mar 2004 (UTC)

Hey! You were only supposed to ask questions I know the answers to! No fair!

Seriously, I haven't seen a lot of footnotes in use, and I couldn't find anything in the style guides or help pages either (and I have more practice looking.) I'm guessing that there isn't a standard format. The format you're using on Debian seems to work, so I'd say go ahead and use that.

In fact, you might even want to add it to the style guides, so that others can see how you did it. You can post a comment about it on the talk page for Manual of Style, with the proposed addition. Put a request for comment in your edit summary, and hopefully a couple people will take a look and give you their thoughts.

Good luck, Isomorphic 00:06, 2 Mar 2004 (UTC)

Re:Wiki Auto
First off, welcome to Wiki Auto! Secondly, you're abosolutely right, there should be a page for the VW Type 2. I was actually thinking about it this morning, while wondering what to add to. The coverage of most vehicle topics in the WP is very limited, so we have loads of scope to play with. I would suggest starting a page at VW Type 2, and creating redirects for alternative names, while mentioning the alternative names at the top of the main article. IMHO the system works best if you create a page first, then ascertain the best name for it later. I'll add VW Type 2 to now. Good luck, can't wait to read it! akaDruid 15:03, 25 Mar 2004 (UTC)

 * Nice work on this article, there is so much info here now! It may almost be worth creating child articles for each revision of the Type 2, since there is so much detail.  I'll see what I can edit/add when I get time, too busy at work for now :(  akaDruid 09:54, 29 Mar 2004 (UTC)

 * I vote for splitting it into one article for the T1-T3, and another for the T4 and T5. There's an obvious break in the continuum there.  ;-)  At the moment however it doesn't seem to make much sense, because the T4/T5 article would be rather short, and while I'm willing to contribute more on the classic Transporters, I just don't know much about the modern stuff.  Therefore, I think it might be best to wait and see whether there'll be T4- and T5-specific additions from other users that make an own article for those worthwhile.  If so, I suggest that that article be called "VW Eurovan", since that's both the model name and the nickname that's used in the US for these vans.  Ermel 19:14, 29 Mar 2004 (UTC)

Hi. I've just removed a link to a disambiguation page from your user page - but there are two more ( Swiss-German ). I wasn't sure whether to redirect them to the countries or the languages - so I've left it for you :). Regards -- sannse (talk) 18:42, 31 Mar 2004 (UTC)

 * Looks fine to me. Thanks. --XTaran | Talk 19:11, 31 Mar 2004 (UTC)

Why thankyou! I just tried to make it as clear and simple as I could. Introductions should always be simple, I think. I'm pondering doing a light copyedit on the body text, but I'm a little reluctant to do that as it's been so long since I read much about engines and my memory might not be up to the task. Best -- Tannin

Engine Types
Hey there. ^_^

Ran across your name on the talk pages of some engine articles which I plan on altering a bit. I was hoping you could help out with the new discussions. As I'm new to Wiki (new to editing anyways, been reading for a while ;)) I was hoping you could help me with input ideas and making sure I'm not being overzealous and blowing other people's stuff up. ;)

Telesque, Apr 26, 2005

Important WikiProject Automobiles Discussion
Hello! As a WikiProject Automobiles member, I just thought you might want to input your opinions on an important discussion we're currently having about whether articles regarding similar vehicles should be merged into one or split by brand. If you would like to comment or read further, please see Wikipedia talk:WikiProject Automobiles. Thank you in advance for your thoughts and feedback. Airline 23:54, 13 February 2006 (UTC)

Wikiproject Automobiles Notification
Hi XTaran, you were on the list of members at WikiProject Automobiles and we are introducing a new way of listing members, as the old list was becoming too long. Our new method involves having all of our members in a category.

To add yourself to the category just add the userbox to your user page by putting   where you want the userbox. Alternatively if you don't like the userbox you can add   to your userpage.

If you no longer wish to be a member of the project, simply don't add the userbox or category, there's no pressure. Thanks for your time, James086Talk 04:41, 17 December 2006 (UTC)

Nomination of Xargs for deletion
A discussion is taking place as to whether the article Xargs is suitable for inclusion in Wikipedia according to Wikipedia's policies and guidelines or whether it should be deleted.

The article will be discussed at Articles for deletion/Xargs until a consensus is reached, and anyone is welcome to contribute to the discussion. The nomination will explain the policies and guidelines which are of concern. The discussion focuses on good quality evidence, and our policies and guidelines.

Users may edit the article during the discussion, including to improve the article to address concerns raised in the discussion. However, do not remove the article-for-deletion template from the top of the article. Ten Pound Hammer • (What did I screw up now?) 00:37, 18 February 2012 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called XTaran. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name XTaran~enwiki that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name. If you think you might own all of the accounts with this name and this message is in error, please visit Special:MergeAccount to check and attach all of your accounts to prevent them from being renamed.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 03:27, 20 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 20:37, 22 April 2015 (UTC)

ArbCom elections are now open!
MediaWiki message delivery (talk) 08:52, 23 November 2015 (UTC)

Proposed deletion of MicroBSD

The article MicroBSD has been proposed for deletion because of the following concern: "lacking sources from July 2008 & notability"

While all constructive contributions to Wikipedia are appreciated, pages may be deleted for any of several reasons.

You may prevent the proposed deletion by removing the notice, but please explain why in your edit summary or on the article's talk page.

Please consider improving the page to address the issues raised. Removing will stop the proposed deletion process, but other deletion processes exist. In particular, the speedy deletion process can result in deletion without discussion, and articles for deletion allows discussion to reach consensus for deletion. Editor-1 (talk) 12:17, 24 December 2018 (UTC)

title: User talk:XTaran~enwiki


text:
William Gordon Claxton

William Gordon Claxton DSO, DFC & Bar (June 1, 1899 – September 28, 1967) was a Canadian World War I flying ace credited with 37 victories. He became the leading ace in his squadron.

Background
Born on June 1, 1899, in Gladstone, Manitoba, Claxton enlisted with the Royal Flying Corps (RFC) in Canada upon his eighteenth birthday in 1917. After pilot's training at Camp Borden, he was assigned to No. 41 Squadron in France the following March flying S.E.5a aircraft. Claxton arrived on the Western Front late in the war but he had a run of victories that saw him emerge from the war as his squadron's most successful airman. He claimed 37 air victories in 79 days during the War's final year. This meteoric career was marked by several multiple victory days. His calmness under fire earned him the nickname "Dozy". It also led him into situations where his planes experienced battle damage. In June 1918 alone, he crash-landed once and brought home shot planes twice.

Career as a fighter pilot
Claxton opened his tally of 'kills' on May 27, 1918, in the skies above East Estaires, downing a German Fokker Dr.I aircraft. The following day he brought down two Pfalz D.III aircraft.

Between June 12 and June 30, Claxton successfully downed 17 German aircraft plus an observation balloon. Thirteen of these planes fell in a four-day stretch, from June 27 through June 30. On June 30, alone he brought down six enemy aircraft. On that incredible day, he flamed a Pfalz D.II, destroyed two Albatros D.Vs, and drove another Pfalz D.III down out of control — all before lunch. In the afternoon, he destroyed yet another Pfalz D.III and shot a DFW C model down in flames. By the end of July, he had increased his total to 27. On August 3, 1918, Claxton was awarded the Distinguished Flying Cross and appointed flight commander. By that time, his victory list had grown to 30.

On August 17, 1918, Claxton was shot down by Leutnant Johannes Gildemeister during an encounter with Jasta 20 in which he and fellow pilot Frederick McCall were outnumbered 20-to-1; by this time he had amassed 37 air successes. In this dogfight, he brought down three enemy planes before being hit. Claxton crash-landed behind enemy lines with a serious head wound and was only saved by prompt attendance of a German doctor, who performed cranial surgery.

Claxton's final score was two observation balloons destroyed, 16 aircraft driven down out of control, and 19 aircraft destroyed. Two of the planes he destroyed were shared victories with 41 Squadron's second ranking ace, Frederick McCall.

Post war
He remained a prisoner of war until the armistice. Claxton was repatriated on December 1, 1918. Returning to his homeland Claxton, who had received a Bar to his DFC and the Distinguished Service Order (DSO) took up a career as a financial journalist.

He died in Toronto on September 28, 1967, aged 68. He was cremated.

Distinguished Flying Cross
"Lt. William Gordon Claxton. This officer at all times shows fine courage and disregard of danger. He has accounted for six enemy aeroplanes and one kite balloon, three of the aeroplanes being destroyed and three driven down out of control. On a recent occasion, having destroyed a hostile balloon, he pursued an enemy scout ten miles and eventually drove it down; he was then attacked by five enemy triplanes and other scouts, but managed to return to our lines, though his machine was riddled with bullets."

Distinguished Flying Cross - Bar
"Lieut. William Gordon Claxton, D.F.C. This officer is conspicuous for his courage in attack. Recently in one day he destroyed six enemy aeroplanes—four in the morning and two in the evening. In thirteen days he accounted for fourteen machines. His utter disregard of danger inspires all who serve with him."

Distinguished Service Order
"Lieut. William Gordon Claxton, D.F.C. Between 4 July and 12 August this officer destroyed ten enemy aeroplanes and one kite balloon, making in all thirty machines and one "kite balloon to his credit. Untiring in attack in the air or on the ground, this officer has rendered brilliant service."

title: William Gordon Claxton


text:
Talk:1980 in Canada

Untitled
Guys are you sure that Clifford Olson raped his first victim Christine Weller? Or he just murdered her?

title: Talk:1980 in Canada


text:
Talk:Finitary relation

This article suxx
It mostly goes over the binary relations material oven and over. Some1Redirects4You (talk) 18:35, 24 April 2015 (UTC)

Theory of relations
There isn't much theory in the Theory of relations wiki article. Just a reiteration of what's here plus a few more definitions. A merge seems in order. Some1Redirects4You (talk) 18:43, 24 April 2015 (UTC)
 * After removing the seemingly WP:OR parts from the "theory" article there wasn't much of substance left in it so I've effected the merge as a redirect. If someone finds some reliable sources (not crowdsourced math wikis) for the material, feel free to restore either here or in its own article if deemed substantive enough. Some1Redirects4You (talk) 14:07, 19 May 2015 (UTC)

Subsets
About this part: "any set (such as the collection of Nobel laureates) can be viewed as a collection of individuals having some property (such as that of having been awarded the Nobel prize)"

Any set is a subset. (That is why there is no set of all sets.) Therefore a unary relation assigns (selects the members of) a subset, not a set just from empty nothing.188.6.76.241 (talk) 16:47, 28 April 2017 (UTC)

Informal introduction
'Mathematically, then, a relation is simply an "ordered set"' — No; it is a set of ordered tuples, not ordered set. Boris Tsirelson (talk) 11:37, 13 February 2018 (UTC)

Second definition
Presently the article contains this definition:
 * Definition 2. A relation L over the sets X1, …, Xk is a (k + 1)-tuple L = (X1, …, Xk, G(L)), where G(L) is a subset of the Cartesian product X1 × … × Xk. G(L) is called the graph of L.

With no reference given, is there an editor defending this definition? — Rgdboer (talk) 23:06, 3 September 2018 (UTC)

As both category theory and relations are concerned with composition (of arrows and of relations, respectively), there is some interplay. Indeed, J. Lambek and P.J. Scott (1986) Introduction to Higher-order Categorical Logic, page 186 describes the category of relations, where the arrows are triples:
 * (α, | f |, β) and f ⊆ α x β.

They write "We often call | f | the graph of f." Further, from the computational point of view, the context of a relation is not to be presumed, so setting the cross product of sets containing the relation is required. Thus software requirements reach into definitions. — Rgdboer (talk) 21:42, 13 September 2018 (UTC)

title: Talk:Finitary relation