Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report)
Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report)
复制标题
Petri 网和交换半群的指数空间完备问题（初步报告）
DOI：
--
复制
发表时间：
1976
期刊：
影响因子：
--
通讯作者：
A. Meyer
中科院分区：
文献类型：
--
作者：
E. Cardoza;R. Lipton;A. Meyer
通勤半群（UWC）的统一单词问题是从任何给定的有限的定义关系集和任何一对单词中确定的问题，这些单词是否描述了由关系定义的交换性元素中的相同元素。 Malcev [1958]和Emilichev [1958]首先明确指出了古典代数问题，尽管回想起来，这一结果可以看作是在König[1903]和Hermann [1926]的早期工作中包含的。
The uniform word problem for commutative semigroups (UWCS) is the problem of determining from any given finite set of defining relations and any pair of words, whether the words describe the same element in the commutative semigroup defined by the relations. The effective decidability of this classical algebraic problem was first explicitly noted by Malcev [1958] and Emilichev [1958], though in retrospect this result can be seen to be contained in the earlier work of König [1903] and Hermann [1926] on polynomial ideals.