Article

Free access

Comprehension and compilation in Optimality Theory

Author:

Jason EisnerAuthors Info & Claims

ACL '02: Proceedings of the 40th Annual Meeting on Association for Computational Linguistics

Pages 56 - 63

https://doi.org/10.3115/1073083.1073095

Published: 06 July 2002 Publication History

Abstract

This paper ties up some loose ends in finite-state Optimality Theory. First, it discusses how to perform comprehension under Optimality Theory grammars consisting of finite-state constraints. Comprehension has not been much studied in OT; we show that unlike production, it does not always yield a regular set, making finite-state methods inapplicable. However, after giving a suitably flexible presentation of OT, we show carefully how to treat comprehension under recent variants of OT in which grammars can be compiled into finite-state transducers. We then unify these variants, showing that compilation is possible if all components of the grammar are regular relations, including the harmony ordering on scored candidates. A side benefit of our construction is a far simpler implementation of directional OT (Eisner, 2000).

References

[1]

Eric Baković. 1999. Assimilation to the unmarked. Rutgers Optimality Archive ROA-340., August.

[2]

Steven Bird. 1995. Computational Phonology: A Constraint-Based Approach. Cambridge.

Digital Library

[3]

Reinhard Blutner. 1999. Some aspects of optimality in natural language interpretation. In Papers on Optimality Theoretic Semantics. Utrecht.

[4]

J. Cole and C. Kisseberth. 1994. An optimal domains theory of harmony. Studies in the Linguistic Sciences, 24(2).

[5]

Jason Eisner. 1997. Efficient generation in primitive Optimality Theory. In Proc. of ACL/EACL.

Digital Library

[6]

Jason Eisner. 2000. Directional constraint evaluation in Optimality Theory. In Proc. of COLING.

Digital Library

[7]

T. Mark Ellison. 1994. Phonological derivation in Optimality Theory. In Proc. of COLING

Digital Library

[8]

J. Eric Fosler. 1996. On reversing the generation process in Optimality Theory. Proc. of ACL Student Session.

Digital Library

[9]

R. Frank and G. Satta. 1998. Optimality Theory and the generative complexity of constraint violability. Computational Linguistics, 24(2):307--315.

Digital Library

[10]

D. Gerdemann and G. van Noord. 2000. Approximation and exactness in finite-state Optimality Theory. In Proc. of ACL SIGPHON Workshop.

[11]

Mark Hale and Charles Reiss. 1998. Formal and empirical arguments concerning phonological acquisition. Linguistic Inquiry, 29:656--683.

[12]

C. Douglas Johnson. 1972. Formal Aspects of Phonological Description. Mouton.

[13]

R. Kaplan and M. Kay. 1994. Regular models of phonological rule systems. Comp. Ling., 20(3).

Digital Library

[14]

L. Karttunen. 1998. The proper treatment of optimality in computational phonology. In Proc. of FSMNLP.

Digital Library

[15]

Kimmo Koskenniemi. 1983. Two-level morphology: A general computational model for word-form recognition and production. Publication 11, Dept. of General Linguistics, University of Helsinki.

[16]

Linda Lombardi. 1999. Positional faithfulness and voicing assimilation in Optimality Theory. Natural Language and Linguistic Theory, 17:267--302.

[17]

Fernando C. N. Pereira and Michael Riley. 1997. Speech recognition by composition of weighted finite automata. In E. Roche and Y. Schabes, eds., Finite-State Language Processing. MIT Press.

[18]

A. Prince and P. Smolensky. 1993. Optimality Theory: Constraint interaction in generative grammar. Ms., Rutgers and U. of Colorado (Boulder).

[19]

Paul Smolensky. 1996. On the comprehension/production dilemma in child language. Linguistic Inquiry, 27:720--731.

Cited By

Karttunen L(2003)Computing with realizational morphologyProceedings of the 4th international conference on Computational linguistics and intelligent text processing10.5555/1791562.1791587(203-214)Online publication date: 16-Feb-2003
https://dl.acm.org/doi/10.5555/1791562.1791587

Comprehension and compilation in Optimality Theory
1. Theory of computation
  1. Formal languages and automata theory

Recommendations

Extending the knowledge compilation map: Krom, Horn, affine and beyond
AAAI'08: Proceedings of the 23rd national conference on Artificial intelligence - Volume 1

We extend the knowledge compilation map introduced by Darwiche and Marquis with three influential propositional fragments, the Krom CNF one (also known as the bijunctive fragment), the Hom CNF fragment and the affine fragment (also known as the ...
Knowledge compilation meets database theory: compiling queries to decision diagrams
ICDT '11: Proceedings of the 14th International Conference on Database Theory

The goal of Knowledge Compilation is to represent a Boolean expression in a format in which it can answer a range of online-queries in PTIME. The online-query of main interest to us is model counting, because of its application to query evaluation on ...
Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams

The goal of Knowledge Compilation is to represent a Boolean expression in a format in which it can answer a range of "online-queries" in PTIME. The online-query of main interest to us is model counting, because of its application to query evaluation on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACL '02: Proceedings of the 40th Annual Meeting on Association for Computational Linguistics

July 2002

543 pages

General Chair:
Pierre Isabelle

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 06 July 2002

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
222
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Karttunen L(2003)Computing with realizational morphologyProceedings of the 4th international conference on Computational linguistics and intelligent text processing10.5555/1791562.1791587(203-214)Online publication date: 16-Feb-2003
https://dl.acm.org/doi/10.5555/1791562.1791587

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents