Consider the "is prefix of" relationship on a set that corresponds to the words of some alphabet. E.g. "ab" is prefix of "abc". This relationship is:

  • antisymmetric
  • transitive
  • reflexive ("ab" is a prefix of "ab")

I understand then that it can be used to define a partially order set.

However, my problem is that the visualization of a partially order set is a Hasse diagram which is a form of DAG. However, I understand the "is prefix of" relationship to be properly resulting in a forest of directed trees. A directed tree is a more specialized data structure than a DAG in that there's at most one path between any two nodes whereas in a DAG you can have more than one. Thinking about the "is prefix of" relationship I don't see how you can get more than one paths between any two words.

E.g. consider the set {"a", "ab", "af", "abc", "abcde", "f", "fg"}

One gets the following forest of trees for the "is prefix of" relationship:



I don't see how one could have another path from the "a" node to the "abcde" node without going through the existing "a, ab, abc, abcde" branch. So it appears that the graph is a directed tree and not just a DAG.

So I think that the "is prefix of" relationship must also have some other property in addition to the three noted above (antisymmetric, transitive, reflexive) that ensures that its Hasse diagram is in fact a tree, and not just a DAG. But which property is that?

  • 1
    $\begingroup$ I guess the property is that if $a\preceq c$ and $b\preceq c$ then either $a\preceq b$ or $b\preceq a$, but I don't know the name for it. $\endgroup$
    – user856
    May 16 '14 at 14:48
  • 1
    $\begingroup$ I've seen this property called "tree-like", but not often enough that I'd consider it standard terminology. $\endgroup$ May 16 '14 at 15:46
  • 2
    $\begingroup$ In Kayne 1994 it's called "locally total": as @Rahul said, it means that the set $\{x : x\le c\}$ is totally ordered for all $c$. I don't think this term is in wide use, though. $\endgroup$
    – user21467
    May 16 '14 at 15:48
  • 2
    $\begingroup$ Oh, and I'd suggest including the empty string, so that the Hasse diagram is really a tree and not a forest. $\endgroup$
    – user21467
    May 16 '14 at 15:49
  • 1
    $\begingroup$ Consider perusing lotpublications.nl/publish/articles/000400/bookpart.pdf :) $\endgroup$ Jun 28 '14 at 19:35

The first thing you should keep in mind is that there is a difference between the Hasse diagram or the corresponding neighbourhood relation and the order itself. The next problematic term is the word “tree”. A tree in graph theory is generally an acyclic graph, which may have some other properties that are fine tuned by the corresponding definition that should be provided.

The relationship you mentioned is a (partial) order (relation) on the given base set. So you don't have to define it. Maybe it helps to know that in order theory partial orders are often called orders and the linearity of an order relation is explicitly spelled out.

The order relation is not a tree or forest in the graph theoretical sense as it contains not only the pairs $(a,ab)$ and $(ab,abc)$, but also $(a,abc)$. Thus, I'd prefer to call it forest order or – if you add the empty string as Steven suggests – tree order. But there are also people around who call the ordered set a tree. There is a difference between the graph theoretic and the order theoretic definitions iff some order ideal (downset) is infinite.

It is easy to prove the tree property if you consider the set of all possible words as a free semigroup, in particular a free monoid, over your alphabet where the neutral element is the empty word. That means all possible words form the base set and your operation $⋅$ is the concatenation. Concatenating a word with the empty word results in the original word. Then the is-prefix-of relation is is the relation: $x≤y :⇔ ∃z:x⋅z = y$. As in the free monoid such an equation has either no solution at all, or the solution is uniqe, the order relation $≤$ is a tree-like order, consequently the induced suborder of any subset is also a forest-like order.

BTW. Between the tree-like orders and the order relations there are also some notions of directed orders (those that countain lower/upper bounds) and semilattices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.