Geodesic
On computation complexity problems concerning relation algebras
Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part IX, Tome 202 (1992), pp. 116-134

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

In this paper, we study the computation complexity of some algebraic combinatorial problems that are closely associated with the graph isomorphism problem. The key point of our considerations is a relation algebra which is a combinatorial analog of a cellular algebra. We present upper bounds on the complexity of central algorithms for relation algebras such as finding the standard basis of extensions and intersection of relation algebras. Also, an approach is described to the graph isomorphism problem involving Schurian relation algebras (these algebras arise from the centralizing rings of permutation groups). We also discuss a number of open problems and possible directions for further investigation. Bibliography: 18 titles. 
@article{ZNSL_1992_202_a6,
     author = {I. N. Ponomarenko},
     title = {On computation complexity problems concerning relation algebras},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {116--134},
     publisher = {mathdoc},
     volume = {202},
     year = {1992},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1992_202_a6/}
}
TY  - JOUR
AU  - I. N. Ponomarenko
TI  - On computation complexity problems concerning relation algebras
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1992
SP  - 116
EP  - 134
VL  - 202
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1992_202_a6/
LA  - ru
ID  - ZNSL_1992_202_a6
ER  - 
%0 Journal Article
%A I. N. Ponomarenko
%T On computation complexity problems concerning relation algebras
%J Zapiski Nauchnykh Seminarov POMI
%D 1992
%P 116-134
%V 202
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1992_202_a6/
%G ru
%F ZNSL_1992_202_a6
I. N. Ponomarenko. On computation complexity problems concerning relation algebras. Zapiski Nauchnykh Seminarov POMI, Computational methods and algorithms. Part IX, Tome 202 (1992), pp. 116-134. http://geodesic.mathdoc.fr/item/ZNSL_1992_202_a6/