[Author Login]
Title:A Note on the Complexity of Optimality Systems
Authors:Christian Wartena
Abstract:A Note on the Complexity of Optimality Systems

Christian Wartena

Universitaet Potsdam

Optimality Theory (OT) has a growing importance in various disciplines of

linguistics. The way in which correct linguistic expressions are generated

according to OT can be captured formally in an Optimality System (OS). An OS

defines a relation between an input and an output using a binary relation,

called GEN, on the domain, and a set of constraints. Frank and Satta (1998)

have shown that an OS in which GEN is a rational relation on strings and which

has only regular constraints defines again a rational relation. This result is

of great importance for phonological applications of OT. For syntax, however,

it cannot be assumed that GEN is a rational relation on strings. Since

OT--syntax is a theory about trees, it seems natural to lift OSs for this

purpose to the domain of trees and relations on trees. It is shown in this

paper that the result concerning regular string languages can be extended to

regular tree languages and it is sketched how such a system might work for

natural language syntax.
Type:Paper/tech report
Article:Version 1