Deciding Identities in Nonassociative Algebras with Dynamic Programming

用动态规划确定非关联代数中的恒等式

• 批准号: 8905534
• 负责人: David Jacobs
• 金额: $ 3.02万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-08-15 至 1992-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8905534&HistoricalAwards=false
• 关键词: Deciding; Identities; Nonassociative; Algebras; Dynamic

This investigation is concerned with algorithms and computational techniques to decide if a given nonassociative polynomial is an identity for a variety of nonassociative algebras. In general, this problem is computationally very difficult, and existing methods suffer from prohibitive time and memory requirements. The approach used in this investigation is to use a dynamic programming algorithm. The algorithm solves the problem by constructing a certain homomorphic image of the free algebra. The number of arithmetic operations required to construct the algebra is bound by a polynomial in the dimension of the resulting algebra (but for many varieties the algorithm might not be polynomial-time in the input size). Using this method, it appears that many questions, which previously appeared to be computationally impractical, may now be solved with existing computers. Preliminary tests show that this method can be used to decide in minutes if certain polynomials, up to degree 10, were identities in the variety of commutative, fourth-power-associative algebras. While the method looks promising, several theoretic issues need to be examined in order to make the method more practical. A goal is to implement the full version of the algorithm on several specific problems. One such problem is the search for Jordan s-identities. Another is determining whether there exist nonspecial Malcev algebras.

这项研究与算法和计算技术有关，以决定给定的非社交多项式是否是多种非缔合代数的身份。 通常，这个问题在计算上非常困难，现有方法遭受了时间和记忆要求的良好。 本研究中使用的方法是使用动态编程算法。 该算法通过构建自由代数的某些同态图像来解决该问题。 构建代数所需的算术操作数量是由多项式在所得代数的尺寸中绑定的（但对于许多品种，算法可能不是输入大小中的多项式时间）。 使用这种方法，似乎许多以前似乎在计算上不切实际的问题现在可以通过现有计算机来解决。 初步测试表明，该方法可在几分钟内决定是否某些多项式（最高10度）是多种多样的，第四次促销缔合的代数中的身份。 尽管该方法看起来很有希望，但需要检查一些理论问题，以使该方法更加实用。 一个目标是在几个特定问题上实现该算法的完整版本。 一个问题是寻找约旦S-身份。 另一个是确定是否存在非专业Malcev代数。