Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups

被引：0

作者：

A. A. Mishchenko

A. V. Treier

机构：

[1] Russian Academy of Sciences,Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch

[2] Omsk State Technical University,Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch

[3] Russian Academy of Sciences,undefined

来源：

Algebra and Logic | 2013年 / 52卷

关键词：

partially commutative nilpotent group; binomial ring; universal theory; satisfiability; decidability;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Let GΓ be a partially commutative group corresponding to a finite simple graph Γ. Given a finite simple graph T, an existential graph formula φ(T) is constructed. We describe an algorithm that answers the question whether φ(T) is satisfied on GΓ, for an arbitrary simple graph T. Using this algorithm, we show that the universal equivalence problem for partially commutative class two nilpotent groups is algorithmically decidable.

引用

页码：147 / 158

页数：11

共 7 条

[1] Ershov YL(1972)Elementary group theories Dokl. Akad. Nauk SSSR 203 1240-1243
[2] Roman’kov VA(1979)Universal theory of nilpotent groups Mat. Zametki. 25 487-495
[3] Timoshenko EI(2010)Universal equivalence of partially commutative metabelian groups Algebra Logika 49 263-290
[4] Myasnikov A(1981)Isomorphisms and elementary properties of nilpotent exponential groups Dokl. Akad. Nauk SSSR 258 1056-1059
[5] Remeslennikov VN(2007)Commutativity graphs for partially commutative class two nilpotent Sib. El. Mat. Izv. 4 460-481
[6] Mishchenko AA(undefined)-groups undefined undefined undefined-undefined
[7] Treier AV(undefined)undefined undefined undefined undefined-undefined

← 1 →