论文标题
井是由有限有序的半群产生的准词
Well quasi-orders arising from finite ordered semigroups
论文作者
论文摘要
1985年，Bucher，Ehrenfeucht和Haussler研究了与给定无上下文规则相关的推导关系。他们的研究激发了关于所有单词半群中的同态性的问题，这些词是有限有序的半群中的问题。问题是，这些同态中的哪一个在所有单词的集合上诱导了准级。我们表明，这个问题是可决定的，答案并不取决于同态，而是有序半群的属性。
In 1985, Bucher, Ehrenfeucht and Haussler studied derivation relations associated with a given set of context-free rules. Their research motivated a question regarding homomorphisms from the semigroup of all words onto a finite ordered semigroup. The question is which of these homomorphisms induce a well quasi-order on the set of all words. We show that this problem is decidable and the answer does not depend on the homomorphism, but it is a property of the ordered semigroup.
