On computation complexity problems concerning relation algebras

DOI10.1007/BF02366131MaRDI QIDQ1329260zbMATH OpenFDO

Authors Ilya Ponomarenko

Publication date 25 July 1994

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02366131

zbMATH Keywords

algebraic combinatoricscomputation complexitygraph isomorphism

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

See the review in Zbl 0807.68036.

Recommendations

• scientific article; zbMATH DE number 4217898
• scientific article; zbMATH DE number 150219
• scientific article; zbMATH DE number 4114007
• Complexity of equational theory of relational algebras with standard projection elements
• scientific article; zbMATH DE number 3936520
• scientific article; zbMATH DE number 3872682
• On the Complexity of the Equational Theory of Relational Action Algebras
• On the complexity of deciding typability in the relational algebra
• The complexity of constraint satisfaction problems for small relation algebras
• Complexity of equations valid in algebras of relations. II: Finite axiomatizations

Cites work

• A note on the graph isomorphism counting problem
• Coherent algebras
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 3841910 (Why is no real title available?)
• scientific article; zbMATH DE number 17523 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Permutation representations
• Polynomial time algorithms for recognizing and isomorphism testing of cyclic tour-naments

Cited in

(9)

• On a new high dimensional Weisfeiler-Lehman algorithm
• Complexity of equations valid in algebras of relations. I: Strong non-finitizability
• scientific article; zbMATH DE number 4217898 (Why is no real title available?)
• Solving Algorithmic Problems on Orders and Lattices by Relation Algebra and RelView
• scientific article; zbMATH DE number 1953891 (Why is no real title available?)
• Complexity of equational theory of relational algebras with standard projection elements
• scientific article; zbMATH DE number 5066582 (Why is no real title available?)
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• The complexity of constraint satisfaction problems for small relation algebras

This page was built for publication: On computation complexity problems concerning relation algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329260)