Complexity of linear order computation in Performance Grammar, TAG and HPSG
Harbusch, K., & Kempen, G.
Complexity of linear order computation in Performance Grammar, TAG and HPSG. In Proceedings of Fifth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+5)
This paper investigates the time and
space complexity of word order computation in the psycholinguistically motivated grammar formalism of Performance Grammar (PG). In PG, the first stage of syntax assembly yields an unordered tree ('mobile') consisting of a hierarchy of
lexical frames (lexically anchored elementary trees). Associated with each lexica l frame is a
linearizer—a Finite-State Automaton that locally computes the left-to-right order of the branches
of the frame. Linearization takes place after the promotion component may have raised certain
constituents (e.g. Wh- or focused phrases) into the domain of lexical frames higher up in the syntactic mobile. We show that the worst-case
time and space complexity of analyzing input strings of length n is O(n5) and O(n4), respectively.
This result compares favorably with the time complexity of word-order computations in Tree Adjoining Grammar (TAG). A comparison
with Head-Driven Phrase Structure Grammar (HPSG) reveals that PG yields a more declarative
linearization method, provided that the FSA is rewritten as an equivalent regular expression.