More Web Proxy on the site http://driver.im/

Article

Free access

Grammars for local and long dependencies

Author:

Alexander DikovskyAuthors Info & Claims

ACL '01: Proceedings of the 39th Annual Meeting on Association for Computational Linguistics

Pages 156 - 163

https://doi.org/10.3115/1073012.1073033

Published: 06 July 2001 Publication History

Abstract

Polarized dependency (PD-) grammars are proposed as a means of efficient treatment of discontinuous constructions. PD-grammars describe two kinds of dependencies: local, explicitly derived by the rules, and long, implicitly specified by negative and positive valencies of words. If in a PD-grammar the number of non-saturated valencies in derived structures is bounded by a constant, then it is weakly equivalent to a cf-grammar and has a O(n³)-time parsing algorithm. It happens that such bounded PD-grammars are strong enough to express such phenomena as unbounded raising, extraction and extraposition.

References

[1]

Y. Bar-Hillel, H. Gaifman, and E. Shamir. 1960. On categorial and phrase structure grammars. Bull. Res. Council Israel, 9F: 1--16.

[2]

N. Bröker. 1998. Separating surface order and syntactic relations in a dependency grammar. In Proc. COLING-ACL, pages 174--180, Montreal.

Digital Library

[3]

A. Ja. Dikovsky and L. S. Modina. 2000. Dependencies on the other side of the Curtain. Traitement Automatique des Langues (TAL), 41(1):79--111.

[4]

A. Dikovsky. 2001. Polarized non-projective dependency grammars. In Ph. De Groote and G. Morrill, editors, Logical Aspects of Computational Linguistics, number 2099 in LNAI. Springer Verlag. To be published.

Digital Library

[5]

H. Gaifman. 1961. Dependency systems and phrase structure systems. Report p-2315, RAND Corp. Santa Monica (CA). Published in: Information and Control, 1965, v. 8, no. 3, pp. 304--337.

[6]

R. A. Hudson. 1984. Word Grammar. Basil Blackwell, Oxford-New York.

[7]

A. K. Joshi, L. S. Levy, and M. Takahashi. 1975. Tree adjunct grammars. Journ. of Comput. and Syst. Sci., 10(1):136--163.

Digital Library

[8]

S. Kahane, A. Nasr, and O. Rambow. 1998. Pseudo-projectivity: A polynomially parsable non-projective dependency grammar. In Proc. COLING-ACL, pages 646--652, Montreal.

Digital Library

[9]

J. Lambek. 1958. The mathematics of sentence structure. American Mathematical Monthly, pages 154--170.

[10]

A. Lecomte. 1992. Proof nets and dependencies. In Proc. of COLING-92, pages 394--401, Nantes.

Digital Library

[11]

V. Lombardo and L. Lesmo. 1996. An earley-type recognizer for dependency grammar. In Proc. 16th COLING, pages 723--728.

Digital Library

[12]

V. Lombardo and L. Lesmo. 1998. Formal aspects and parsing issues of dependency theory. In Proc. COLING-ACL, pages 787--793, Montreal.

Digital Library

[13]

I. Mel'čuk and N. V. Pertsov. 1987. Surface Syntax of English. A Formal Model Within the Meaning-Text Framework. John Benjamins Publishing Company, Amsterdam/Philadelphia.

[14]

M. Moortgat. 1990. La grammaire catégorielle généralisée: le calcul de lambek-gentzen. In Ph. Miller and Th. Torris, editors, Structure of languages and its mathematical aspects, pages 127--182. Hermes, Paris.

[15]

A. Nasr. 1995. A formalism and a parser for lexicalized dependency grammars. In Proc. Int. Workshop on Parsing Technology, pages 186--195, Prague.

[16]

P. Neuhaus and N. Bröker. 1997. The Complexity of Recognition of Linguistically Adequate Dependency Grammars. In Proc. of 35th ACL Annual Meeting and 8th Conf. of the ECACL, pages 337--343.

Digital Library

[17]

Jane J. Robinson. 1970. Dependency structures and transformational rules. Language, 46(2):259--285.

[18]

D. D. Sleator and D. Temperly. 1993. Parsing English with a Link Grammar. In Proc. IWPT'93, pages 277--291.

[19]

L. Tesnière. 1959. Éléments de syntaxe structurale. Librairie C. Klincksieck, Paris.

Cited By

Dekhtyar MDikovsky AKarlov B(2019)Categorial dependency grammarsTheoretical Computer Science10.1016/j.tcs.2015.01.043579:C(33-63)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2015.01.043
Karlov B(2012)Abstract automata and a normal form for categorial dependency grammarsProceedings of the 7th international conference on Logical Aspects of Computational Linguistics10.1007/978-3-642-31262-5_6(86-102)Online publication date: 2-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31262-5_6
Dekhtyar MDikovsky A(2008)Generalized categorial dependency grammarsPillars of computer science10.5555/1805839.1805852(230-255)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1805839.1805852
Show More Cited By

Grammars for local and long dependencies
1. Theory of computation

Recommendations

Parsing expression grammars: a recognition-based syntactic foundation
POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...
Long-distance dependencies and Applicative Universal Grammar
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 2

To deal with long-distance dependencies, Applicative Universal Grammar (AUG) proposes a new type of categorial rules, called superposition rules. We compare the AUG rules with the alternative rules of Steedman's Combinatory Categorial Grammar (CCG) (...
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04

For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACL '01: Proceedings of the 39th Annual Meeting on Association for Computational Linguistics

July 2001

562 pages

General Chair:
Bonnie Lynn Webber

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 06 July 2001

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
214
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)5

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dekhtyar MDikovsky AKarlov B(2019)Categorial dependency grammarsTheoretical Computer Science10.1016/j.tcs.2015.01.043579:C(33-63)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2015.01.043
Karlov B(2012)Abstract automata and a normal form for categorial dependency grammarsProceedings of the 7th international conference on Logical Aspects of Computational Linguistics10.1007/978-3-642-31262-5_6(86-102)Online publication date: 2-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31262-5_6
Dekhtyar MDikovsky A(2008)Generalized categorial dependency grammarsPillars of computer science10.5555/1805839.1805852(230-255)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1805839.1805852
Béchet DDikovsky AForet A(2005)Dependency structure grammarsProceedings of the 5th international conference on Logical Aspects of Computational Linguistics10.1007/11422532_2(18-34)Online publication date: 28-Apr-2005
https://dl.acm.org/doi/10.1007/11422532_2

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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