Derivation languages and syntactical categories

Derivations in unrestricted phrase structure grammars are represented in terms of a string called a derivation word. The derivation word gives a very compact representation of the canonical (leftmost) derivation. An algebra of derivation words is developed to give a concrete realization to the categorical treatment of derivations due to Hotz. In particular, derivation composition and juxtaposition are defined for derivation words, and effective techniques are given for obtaining the domain and codomain functions. All of the algorithms can be performed in linear time and space