{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T15:48:42Z","timestamp":1762271322033},"reference-count":6,"publisher":"MIT Press - Journals","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p> Given a constraint set with k constraints in the framework of Optimality Theory (OT), what is its capacity as a classification scheme for linguistic data? One useful measure of this capacity is the size of the largest data set of which each subset is consistent with a different grammar hypothesis. This measure is known as the Vapnik-Chervonenkis dimension (VCD) and is a standard complexity measure for concept classes in computational learnability theory. In this work, I use the three-valued logic of Elementary Ranking Conditions to show that the VCD of Optimality Theory with k constraints is k-1. Analysis of OT in terms of the VCD establishes that the complexity of OT is a well-behaved function of k and that the \u2018hardness\u2019 of learning in OT is linear in k for a variety of frameworks that employ probabilistic definitions of learnability. <\/jats:p>","DOI":"10.1162\/coli.07-031-r2-06-98","type":"journal-article","created":{"date-parts":[[2009,1,23]],"date-time":"2009-01-23T22:10:25Z","timestamp":1232748625000},"page":"47-59","source":"Crossref","is-referenced-by-count":11,"title":["The Complexity of Ranking Hypotheses in Optimality Theory"],"prefix":"10.1162","volume":"35","author":[{"given":"Jason","family":"Riggle","sequence":"first","affiliation":[{"name":"* Department of Linguistics, University of Chicago, 1010 E. 59th St., Chicago, IL 60637.."}]}],"member":"281","reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"p_3","first-page":"43","volume":"21","author":"Boersma Paul","year":"1997","journal-title":"Proceedings of the Institute of Phonetic Sciences"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1162\/002438901554586"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/coli.07-031-R2-06-98","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:25:23Z","timestamp":1615584323000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/35\/1\/47-59\/2008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":6,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1162\/coli.07-031-R2-06-98"],"URL":"https:\/\/doi.org\/10.1162\/coli.07-031-r2-06-98","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]}}}