Tree Languages
Andrei Kelarev · 2003
Theorem 8.1. ([164]) The graph algebra o f a graph D is the syntactic algebra o f a tree language if and only if the following conditions hold: (i) all vertices o f in-degree zero have pairwise distinct out-neighbourhoods in D; (ii) D does not have three vertices with equal in-neighbourhoods and equal out-neighbourhoods.