Formal Properties and Implementation of Bidirectional Charts
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Speech and Natural Language. 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.
@inproceedings{ijcai1989p236,
title = {Formal Properties and Implementation of Bidirectional Charts},
author = {Satta, Giorgio and Stock, Oliviero},
booktitle = {Proceedings of the Eleventh International Joint Conference on
Artificial Intelligence, {IJCAI-89}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {N. S. Sridharan},
pages = {1480--1484},
year = {1989},
month = {8},
note = {Speech and Natural Language},
url = {https://ijcai.org/proceedings/1989/236},
}
TY - CPAPER TI - Formal Properties and Implementation of Bidirectional Charts AU - Satta, Giorgio AU - Stock, Oliviero T2 - Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 PB - International Joint Conferences on Artificial Intelligence PY - 1989 SP - 1480 EP - 1484 UR - https://ijcai.org/proceedings/1989/236 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
