# OT grammars, beyond partial orders: ERC sets and antimatroids

@article{Merchant2016OTGB, title={OT grammars, beyond partial orders: ERC sets and antimatroids}, author={Nazarr{\'e} Merchant and Jason Riggle}, journal={Natural Language \& Linguistic Theory}, year={2016}, volume={34}, pages={241-269} }

Grammars in Optimality Theory can be characterized by sets of Elementary Ranking Conditions (ERCs). Antimatroids are structures that arose initially in the study of lattices. In this paper we prove that antimatroids and consistent ERC sets have the same formal structures. We do so by defining two functions Antimat and RCErc, Antimat being a function from consistent sets of ERCs to antimatroids and RCErc a function from antimatroids to ERC sets. We then show that these functions are inverses of… Expand

#### References

SHOWING 1-10 OF 16 REFERENCES

Ranking and necessity: the Fusional Reduction Algorithm

- Sociology
- 2011

Understanding a linguistic theory within OT requires an exact characterization of the ranking conditions necessitated by data. These conditions determine the formal shape of the grammar while… Expand

The Complexity of Ranking Hypotheses in Optimality Theory

- Computer Science
- Computational Linguistics
- 2009

This work uses the three-valued logic of Elementary Ranking Conditions to show that the VCD of Optimality Theory with k constraints is k-1 and establishes that the complexity of OT is a well-behaved function of k and that the hardness of learning in OT is linear in k for a variety of frameworks that employ probabilistic definitions of learnability. Expand

Discovering underlying forms: Contrast pairs and ranking

- Computer Science
- 2008

This dissertation proposes a learning algorithm that attends to pairs of overt forms that differ in exactly one morpheme, which can exhibit less ambiguity than the isolated overt forms, while still providing a reduced search space. Expand

Optimality Theory: Constraint Interaction in Generative Grammar

- Mathematics
- 2004

Prefactory Note. Acknowledgments. 1. Preliminaries:. Background and Overview. Optimality. Overall Structure of the Argument. Overview of Part I. 2. Optimality in Grammar: Core Syllabification in… Expand

Lattices with Unique Irreducible Decompositions

- Mathematics
- 1940

Consider a lattice S in which the ascending chain condition holds. Then each element of S has at least one reduced1 representation as a cross-cut of irreducibles. Now it is well known that the… Expand

A circuit set characterization of antimatroids

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 1987

Rooted circuits of anitmatroids are defined, and a new characterization of antimatroids involves a rooted circuit eliminationproperty that is reminiscent of the matroid circuit elimination property. Expand

Some Mathematical Structures Underlying Efficient Planning

- Mathematics
- 2003

We explore antimatroids ,a lso known as shelling structures, ac onstruct used to formalize when greedy (local) algorithms are optimal, as well as their relation to the strong measure of progressP… Expand

Doing Optimality Theory: Applying Theory to Data

- Mathematics
- 2008

Acknowledgments. Read This First!. List of Abbreviations. 1. An Introduction to Optimality Theory. 1.1 How OT Began. 1.2 Why Must Constraints Be Violable?. 1.3 The Nature of Constraints in OT. 1.4… Expand

Matroids and antimatroids - a survey

- Mathematics, Computer Science
- Discret. Math.
- 1989

Similarities and differences between matroids and antimatroids (abstract dependence systems) are discussed and several analogous characterizations of these structures are compared. Expand

Multilingual learning with parameter co-occurrence clustering

- Computer Science
- 2007

A fundamental question, then, is how language learners in a pervasively multilingual environment, where they receive mixed samples from many distinct linguistic systems, can manage to distinguish the component systems and acquire them separately. Expand