|
This article is cited in 3 scientific papers (total in 3 papers)
Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups
A. A. Mishchenkoab, A. V. Treierba a Omsk State Technical University, Omsk, Russia
b Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Omsk, Russia
Abstract:
Let $G_\Gamma$ be a partially commutative group corresponding to a finite simple graph $\Gamma$. Given a finite simple graph $T$, an existential graph formula $\phi(T)$ is constructed. We describe an algorithm that answers the question whether $\phi(T)$ is satisfied on $G_\Gamma$, 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.
Keywords:
partially commutative nilpotent group, binomial ring, universal theory, satisfiability, decidability.
Received: 24.08.2012
Citation:
A. A. Mishchenko, A. V. Treier, “Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups”, Algebra Logika, 52:2 (2013), 219–235; Algebra and Logic, 52:2 (2013), 147–158
Linking options:
https://www.mathnet.ru/eng/al583 https://www.mathnet.ru/eng/al/v52/i2/p219
|
Statistics & downloads: |
Abstract page: | 515 | Full-text PDF : | 56 | References: | 35 | First page: | 19 |
|