Paper: Switch Graphs For Parsing Type Logical Grammars

ACL ID W05-1503
Title Switch Graphs For Parsing Type Logical Grammars
Venue Workshop On Parsing Technology
Year 2005

Parsing in type logical grammars amounts to theorem proving in a substructural logic. This paper takes the proof net presentation of Lambek’s associative cal- culus as a case study. It introduces switch graphs for online maintenance of the Danos-Regnier acyclicity condi- tion on proof nets. Early detection of Danos-Regnier acyclicity violations sup- ports early failure in shift-reduce parsers. Normalized switch graphs represent the combinatorial potential of a set of anal- yses derived from lexical and structural ambiguities. Packing these subanalyses and memoizing the results leads directly to a dynamic programming algorithm for Lambek grammars.

  author    = {Carpenter, Bob  and  Morrill, Glyn},
  title     = {Switch Graphs for Parsing Type Logical Grammars},
  booktitle = {Proceedings of the Ninth International Workshop on Parsing Technology},
  month     = {October},
  year      = {2005},
  address   = {Vancouver, British Columbia},
  publisher = {Association for Computational Linguistics},
  pages     = {18--29},
  url       = {}