Tree correspondence problems
作者：
Highlights：
•
摘要
We investigate decision problems for the concatenation of rooted trees, considering different types of trees as well as different modes of concatenation. Our main theorem establishes the undecidability of the following problem: Given two lists A = (x1,…, xk) and B = (y1,…, yk) of rooted ordered unlabeled trees, does there exist a sequence of indices i1, …, in such that the concatenation of xi1, xi2, …, Xin, —in that order—equals the concatenation of yi1,yi2,…,yin, in that order?
论文关键词：
论文评审过程：Received 14 November 1980, Revised 11 September 1981, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(82)90046-0
