Geodesic
Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups
Algebra i logika, Tome 52 (2013) no. 2, pp. 219-235

Voir la notice de l'article provenant de la source Math-Net.Ru

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, universal theory, satisfiability, decidability.
Mots-clés : binomial ring 
@article{AL_2013_52_2_a5,
     author = {A. A. Mishchenko and A. V. Treier},
     title = {Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups},
     journal = {Algebra i logika},
     pages = {219--235},
     publisher = {mathdoc},
     volume = {52},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2013_52_2_a5/}
}
TY  - JOUR
AU  - A. A. Mishchenko
AU  - A. V. Treier
TI  - Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups
JO  - Algebra i logika
PY  - 2013
SP  - 219
EP  - 235
VL  - 52
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2013_52_2_a5/
LA  - ru
ID  - AL_2013_52_2_a5
ER  - 
%0 Journal Article
%A A. A. Mishchenko
%A A. V. Treier
%T Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups
%J Algebra i logika
%D 2013
%P 219-235
%V 52
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2013_52_2_a5/
%G ru
%F AL_2013_52_2_a5
A. A. Mishchenko; A. V. Treier. Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups. Algebra i logika, Tome 52 (2013) no. 2, pp. 219-235. http://geodesic.mathdoc.fr/item/AL_2013_52_2_a5/