A tabular interpretation of a class of 2-Stack Automata

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.

Eric Villemonte de la Clergerie / Eric.Clergerie@inria.fr
Miguel Angel Alonso Pardo / alonso@dc.fi.udc.es