... cases.¹

Although in some cases such a direct implementation can be much more efficient [17,24].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... transduction²

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:³

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.⁴

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:⁵

The operators `o' and `lc' are assumed to be left associative and have equal precedence.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...tex2html_verb_mark⁶

As explained in footnote 2, this will be coerced into an identity transducer.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... constituents.⁷

This construction is similar to the construction in [3], who used a suggestion in [2].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... example:⁸

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.⁹

[7] compares containment theory and correspondence theory for the syllable structure example.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... [a,1].¹⁰

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.¹¹

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.¹²

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.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.