Springer Verlag, Studia Logica, 2-3(87), p. 171-197
DOI: 10.1007/s11225-007-9087-0
Full text: Download
Pregroup grammars have a cubic recognition algorithm. Here, we define a correct and complete recognition and parsing algorithm and give sufficient conditions for the algorithm to run in linear time. These conditions are satisfied by a large class of pregroup grammars, including grammars that handle coordinate structures and distant constituents.