- ... cases.
^{1} - Although in some cases such a direct
implementation can be much more efficient
[17,24].
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... transduction
^{2} - If an expression for a recognizer occurs
in a context where a transducer is required, the identity operation
will be used implicitly for coercion.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... as:
^{3} - The notation
`macro(Expr1,Expr2)`is used to indicate that the regular expression`Expr1`is an abbreviation for the expression`Expr2`. Because Prolog variables are allowed in both expressions this turns out to be an intuitive and powerful notation [24].. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
operator.
^{4} - An alternative would be to define
*overparse*with a Kleene star in place of the option operator. This would introduce unbounded sequences of empty segments. Even though it can be shown that, with the constraints assumed here, no optimal candidate ever contains two empty segments in a row (proposition 4 of [19]) it is perhaps interesting to note that defining*Gen*in this alternative way causes cases of infinite ambiguity for the counting approach but is unproblematic for the matching approach.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... candidates:
^{5} - The operators `o'
and `lc' are assumed to be left associative and have equal
precedence.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...tex2html_verb_mark
^{6} - As explained in
footnote 2, this will be coerced into an identity
transducer.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
constituents.
^{7} - This construction is similar to the
construction in [3], who used a suggestion in
[2].
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... example:
^{8} - An
alternative approach would be to
compose the
`permute_marker`transducers before inserting extra markers. Our tests, however, show this alternative to be somewhat less efficient.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
matching.
^{9} - [7] compares containment theory and
correspondence theory for the syllable structure example.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... [a,1].
^{10} - OT makes a fundamental
distinction between
*markedness*constraints (referring only to the surface) and*faithfulness*constraints (referring to both surface and underlying form). With this mark-up convention, faithfulness constraints might be allowed to refer to both symbols marked with 0 and symbols marked with 1. But note that the`Fill`and`Parse`constraints in syllabification are also considered to be faithfulness constraints since they correspond to epenthesis and deletion respectively.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
OT.
^{11} - Matching with local permutation is not strictly more
powerful than counting. For an example, change
*Gen*in this example to:`{[([] x a),{b,c}*],[{b,c}*,([] x [a,a])]}`. This can be exactly implemented by counting with a precision of one. Matching with local permutation, however, cannot exactly implement this case, since markers would need to be permuted across unbounded sequences.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...roch:lang97.
^{12} - We have adapted the algorithm proposed in
[20] since it fails to treat certain types of
transducer correctly; we intend to provide details somewhere else.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .