Geodesic
Algorithmic decidability of the universal equivalence problem for partially commutative nilpotent groups
Algebra i logika, Tome 52 (2013) no. 2, pp. 219-235
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2013},
     volume = {52},
     number = {2},
     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
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
%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/

[1] Yu. L. Ershov, “Ob elementarnykh teoriyakh grupp”, Dokl. AN SSSR, 203:6 (1972), 1240–1243 | MR | Zbl

[2] V. A. Romankov, “Ob universalnoi teorii nilpotentnykh grupp”, Matem. zametki, 25:4 (1979), 487–495 | MR | Zbl

[3] A. A. Mischenko, “Ob universalnoi ekvivalentnosti chastichno kommutativnykh dvustupenno nilpotentnykh $\mathbb Q$-grupp”, Vest. Omsk. un-ta, 2008, Spets. vypusk, 93–100

[4] E. I. Timoshenko, “Universalnaya ekvivalentnost chastichno kommutativnykh metabelevykh grupp”, Algebra i logika, 49:2 (2010), 263–290 | MR | Zbl

[5] A. G. Myasnikov, V. N. Remeslennikov, “Izomorfizmy i elementarnye svoistva nilpotentnykh stepennykh grupp”, Dokl. AN SSSR, 258:5 (1981), 1056–1059 | MR | Zbl

[6] A. A. Mischenko, A. V. Treier, “Struktura tsentralizatorov dlya chastichno kommutativnoi dvustupenno nilpotentnoi $\mathbb Q$-gruppy”, Vest. Omsk. gos. un-ta, 2007, Spets. vypusk, 98–102

[7] C. C. Chang, H. J. Keisler, Model theory, Stud. Logic Found. Math., 73, North-Holland Publ. Co., Amsterdam–London, New York, 1973 | MR | Zbl

[8] A. A. Mischenko, A. V. Treier, “Grafy kommutativnosti dlya chastichno kommutativnykh dvustupenno nilpotentnykh $\mathbb Q$-grupp”, Sib. elektron. matem. izv., 4 (2007), 460–481 http://semr.math.nsc.ru/v4/p460-481.pdf | MR | Zbl

[9] A. A. Mischenko, A. V. Treier, “O vypolnimosti grafovykh formul na chastichno kommutativnoi dvustupenno nilpotentnoi gruppe”, Algebra i teoriya modelei, Cb. tr., 8, eds. A. G. Pinus i dr., izd-vo NGTU, Novosibirsk, 2011, 48–59