In evolutionary linguistics, a structure often encountered are so-called syntactic trees. Starting out with a graph-theoretic tree $T=(V,E)$, we can designate one specific vertex $v \in V$ as the root, which produces a rooted tree $(T,v)$. On rooted trees, one can define the notions of parent and child vertices. Next, an ordered tree is a rooted tree $(T,v)$ together with a total ordering on the children $\leq_u$ of any vertex $u \in V$. These local orderings then allow a linearization of the vertices, i.e.\ an algorithmic total ordering on all vertices. Using formal language theory, one can show that any context-free language produces derivation trees. Such trees are always ordered trees, and since many vertices may have the same label, one must work with labeled ordered trees.

This talk will showcase the structure of syntactic trees as neurolinguistically motivated mathematical problem. Starting with trees, the talk will show how rooting a tree gives it several implicit properties: Rooted trees have a preferred orientation given by orienting all edges away from the root, which induces a partial ordering $\leq$ on the vertices $V$. Moreover, to every vertex $u \in V$ one can assign its height $h(u)$, namely its distance to the root. Next, the talk will move to ordered trees and show off the lexicographical ordering, which corresponds exactly to performing depth-first search, as an example of a linearization algorithm that also preserves the local orderings. The talk will conclude with an answer to the mathematical problem by showing that performing depth-first search on the leaves of any linguistic syntactic tree, which is a special case of a labeled ordered tree, yields exactly the underlying sentence.