  The sequential structure of language, and the order of words in a sentence
specifically, plays a central role in human language processing. Consequently,
in designing computational models of language, the de facto approach is to
present sentences to machines with the words ordered in the same order as in
the original human-authored sentence. The very essence of this work is to
question the implicit assumption that this is desirable and inject theoretical
soundness into the consideration of word order in natural language processing.
In this thesis, we begin by uniting the disparate treatments of word order in
cognitive science, psycholinguistics, computational linguistics, and natural
language processing under a flexible algorithmic framework. We proceed to use
this heterogeneous theoretical foundation as the basis for exploring new word
orders with an undercurrent of psycholinguistic optimality. In particular, we
focus on notions of dependency length minimization given the difficulties in
human and computational language processing in handling long-distance
dependencies. We then discuss algorithms for finding optimal word orders
efficiently in spite of the combinatorial space of possibilities. We conclude
by addressing the implications of these word orders on human language and their
downstream impacts when integrated in computational models.
