Containment.

It might be objected that the Prince and Smolensky syllable structure example is a particularly simple containment theory analysis and that other varieties of OT such as correspondence theory [16] are beyond the scope of matching.⁹ Indeed we have relied on the fact that Gen only adds brackets and does not add or delete anything from the set of input symbols. The filter that we construct needs to compare candidates with alternative candidates generated from the same input.

If Gen is allowed to change the input then a way must be found to remember the original input. Correspondence theory is beyond the scope of this paper, however a simple example of an OT where Gen modifies the input is provided by the problem described in §2.2 (from [3]). Suppose we modify Gen here so that its output includes a representation of the original input. One way to do this would be to adopt the convention that input symbols are marked with a following 0 and output symbols are marked with a following 1. With this convention Gen becomes:

macro(gen, 
 {[(a x [a,0,b,1])*,(b x [b,0,a,1])*], 
  [(a x [a,0,a,1])*,(b x [b,0,b,1])*]})

Then the constraint against the symbol a needs to be recast as a constraint against [a,1].¹⁰ And, whereas above add_violation was previously written to ignore brackets, for this case it will need to ignore output symbols (marked with a 1). This approach is easily implementable and with sufficient use of permutation, an approximation can be achieved for any predetermined bound on input length.