In this paper we analyze the complexity of Harmonic Grammar (HG), a linguistic model in which licit underlying form to surface form mappings are determined by optimization over weighted constraints. We show that the Vapnik-Chervonenkis Dimension of HG grammars with k constraints is k-1. This is the same as the VC dimension of Optimality Theory (OT), which is similar to HG, but uses ranked rather than weighted constraints in optimization. The parity of the VC dimension in these models is surprising because OT defines finite classes of languages — there are at most k! ways to rank k constraints — while HG defines infinite classes of languages. The linear growth of the VC dimension with the number of constraints has broad positive ramifications for the learnability of HG grammars.

The citation of the paper is as follows:

Bane, Max and Jason Riggle. To appear. Three correlates of the typological frequency of quantity-insensitive stress systems.

A copy of the paper is available on ROA as document number 966.

Here is the abstract of the paper:

We examine the typology of quantity-insensitive (QI) stress systems and ask to
what extent an existing optimality theoretic model of QI stress can predict
the observed typological frequencies of stress patterns. We find three
significant correlates of pattern attestation and frequency: the trigram
entropy of a pattern, the degree to which it is “confusable” with other
patterns predicted by the model, and the number of constraint rankings that
specify the pattern.