[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Categorial Grammars with Iterated Types form a Strict Hierarchy of k-Valued Languages

  • Conference paper
Implementation and Application of Automata (CIAA 2011)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6807))

Included in the following conference series:

Abstract

The notion of k-valued categorial grammars where a word is associated to at most k types is often used in the field of lexicalized grammars as a fruitful constraint for obtaining several properties like the existence of learning algorithms. This principle is relevant only when the classes of k-valued grammars correspond to a real hierarchy of languages. Such a property had been shown earlier for classical categorial grammars.

This paper establishes the relevance of this notion when categorial grammars are enriched with iterated types.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bar-Hillel, Y.: A quasi arithmetical notation for syntactic description. Language 29, 47–58 (1953)

    Article  MATH  Google Scholar 

  2. Béchet, D., Dikovsky, A., Foret, A.: Two models of learning iterated dependencies. In: Proc. of the 15th Conference on Formal Grammar (FG 2010), Copenhagen, Denmark. LNCS (2010) (to appear), http://www.angl.hu-berlin.de/FG10/fg10_list_of_papers

  3. Béchet, D., Dikovsky, A., Foret, A., Moreau, E.: On learning discontinuous dependencies from positive data. In: Proc. of the 9th Intern. Conf. Formal Grammar (FG 2004), Nancy, France, pp. 1–16 (2004)

    Google Scholar 

  4. Béchet, D., Foret, A.: k-valued non-associative lambek grammars (Without product) form a strict hierarchy of languages. In: Blache, P., Stabler, E.P., Busquets, J.V., Moot, R. (eds.) LACL 2005. LNCS (LNAI), vol. 3492, pp. 1–17. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  5. Dekhtyar, M., Dikovsky, A.: Generalized categorial dependency grammars. In: Avron, A., Dershowitz, N., Rabinovich, A. (eds.) Pillars of Computer Science. LNCS, vol. 4800, pp. 230–255. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  6. Dikovsky, A.: Dependencies as categories. In: Recent Advances in Dependency Grammars (COLING 2004) Workshop, pp. 90–97 (2004)

    Google Scholar 

  7. Gold, E.: Language identification in the limit. Information and control 10, 447–474 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  8. Joshi, A.K., Shabes, Y.: Tree-adjoining grammars and lexicalized grammars. In: Tree Automata and LGS, Elsevier Science, Amsterdam (1992)

    Google Scholar 

  9. Kanazawa, M.: Learnable Classes of Categorial Grammars. In: Studies in Logic, Language and Information, Center for the Study of Language and Information (CSLI) and The European association for Logic, Language and Information (FOLLI), Stanford, California (1998)

    Google Scholar 

  10. Karlov, B.: On properties of generalized categorial dependency grammars. In: Proc. of the 12th National Conference on Artificial Intelligence, Russia, vol. 1, pp. 283–290 (2010)

    Google Scholar 

  11. Lambek, J.: The mathematics of sentence structure. American mathematical monthly 65 (1958)

    Google Scholar 

  12. Mel’čuk, I.: Dependency Syntax. SUNY Press, Albany (1988)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Béchet, D., Dikovsky, A., Foret, A. (2011). Categorial Grammars with Iterated Types form a Strict Hierarchy of k-Valued Languages. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, JM., Maurel, D. (eds) Implementation and Application of Automata. CIAA 2011. Lecture Notes in Computer Science, vol 6807. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22256-6_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-22256-6_5

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-22255-9

  • Online ISBN: 978-3-642-22256-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics