Paper: A tabular interpretation of a class of 2-Stack Automata

ACL ID P98-2217
Title A tabular interpretation of a class of 2-Stack Automata
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1998
Authors

The paper presents a tabular interpretation for a kind of 2-Stack Automata. These automata may be used to describe various parsing strategies, ranging from purely top-down to purely bottom-up, for LIGs and TAGs. The tabular interpretation ensures, for all strategies, a time complexity in O(n 6) and space complexity in O(n 5) where n is the length of the input string.