Topological sorting and well-formed strings 1

Abstract

A topological sorting of a tree is a linear ordering of its elements that preserves and extends their partial ordering in the tree. Any such arrangement of tree elements has a characteristic property, involving collective weights of initial or final substrings. Such properties have been investigated in connection with random walks, combinatorial arrangements, and the well-formed strings of parenthesis-free notations. Topological sortings of directed acyclic graphs exhibit a similar structure.