Eric Villemonte de la Clergerie
Miguel Angel Alonso Pardo
in COLING-ACL'98, 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Proceedings of the Conference, volume II, pp. 1333-1339, Montreal, Canada, 1998.
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(n6) and space complexity in O(n5) where n is the length of the input string.