可量词消去的带根节点的树理论

The Classification of All Quantifier-Eliminable Directed or Undirected Trees with a Root

讨论了带根节点r的有向树、无向树理论的量词消去性质,找到决定理论量词消去的三类特殊公式,并给出了在语言■_0={E,r}(E为有向边或无向边)及添加二元距离关系D_(n,n)<w所得膨胀语言下,可量词消去的这两类理论的完全分类.

We put forward three special formulas to describe the structural characteristics of directed or undirected trees with a root.On this basis,quantifier elimination property for directed or undirected trees with root r in the language L0= {E,r} and its expansion is discussed and four classification results are proposed.