<OT> Re: Quadratic Alignment Constrants and Finite State Optimality Theory

[Jason Eisner]

> Quadratic Alignment Constraints and Finite State Optimality Theory
> Tamás Bíró <birot@let.rug.nl>
> Direct link: http://roa.rutgers.edu/view.php3?roa=600

Hi Tamás,

I don't usually plug my work on this list, but I'm afraid it's not a
new observation that GA constraints count up quadratically many
violations, or that this is beyond the ability of finite-state
devices.  See section 4.1 of Eisner 1997 (ACL).

Your paper also says that "future work" should prove that the ranking
or filtering effect of a quadratic GA constraint cannot be achieved by
some other finite-state device.  This too was shown in the above
reference; write to me for full proof details.

Note that a quadratic number of violations is not by itself a problem.
Consider the hypothetical constraint "NoCodaSquared," which assigns
n*n violations to a candidate with n codas.  This has a quadratic
number of violations, but imposes exactly the same ranking on
candidates as NoCoda does.  So its effect can be captured just as well
by a transducer that counts linearly 1,2,3 ... (or 2,4,6 ...) instead
of quadratically 1,4,9 ...

In the same way, most phonologists use quadratic GA constraints only
to do work that could also be done by harmless finite-state devices.
Not surprising, since they're describing phonologies.  But the GA
mechanism unfortunately does have more power -- it can be used to
describe linguistically unattested, computationally non-finite-state
phenomena.

It was to respond to this concern that I developed a completely
GA-free, finite-state OT account of metrical stress typology (also in
1997).

As you seem to be interested in cutting back OT's power to that of
regular relations, you might also look at papers that I wrote in 2000
and 2002.  Particularly the work on directional constraint evaluation.
Quadratic constraints (as you note) prevent you from using an FST to
count violations.  Even linear constraints (as Frank & Satta noted)
are powerful enough to prevent you from using an FST to map between
underlying and surface forms.  Directional constraint evaluation
neatly eliminates both problems, thereby improving OT's explanatory
adequacy -- while apparently retaining descriptive adequacy.

Best place to get any of these papers is
   http://cs.jhu.edu/~jason/papers/narrative.html#sec-ot
although some are also on the ROA.  

cheers,
jason eisner (johns hopkins univ.)