---
title: "Formal Properties and Implementation of Bidirectional Charts"
authors:
  - "Giorgio Satta"
  - "Oliviero Stock"
doi: ""
url: "https://ijcai.org/proceedings/1989/236"
pdf: "https://ijcai.org/proceedings/1989/0236.pdf"
venue: "Proceedings of the Eleventh International Joint Conference on Artificial Intelligence"
year: 1989
pages: "1480-1484"
track: "Speech and Natural Language"
keywords:
---

# Formal Properties and Implementation of Bidirectional Charts

Giorgio Satta, Oliviero Stock

*Proceedings of the Eleventh International Joint Conference on Artificial Intelligence*, pages 1480-1484.

## Abstract

Several theories of grammar currently converge toward inserting subcategorization information within lexical entries. Such a tendency would benefit from a parsing algorithm able to work from "triggering positions" outward. In this paper a bidirectional extension of the chart algorithm is proposed and its most relevant formal properties are investigated using an Earley like formalism. The question as to whether the proposed approach guarantees computational feasibility is then addressed and is answered affirmatively. Also, it is shown that the method presented here maintains those characteristics that were so much appreciated in monodirectional charts. Finally, from this analysis indications are derived for an efficient implementation of the parsing algorithm.