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)

zbMATH Keywords

graph isomorphismalgebraic combinatoricscomputation complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4217898
• scientific article; zbMATH DE number 150219
• Publication:4729350
• 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

• 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?)
• A note on the graph isomorphism counting problem
• Coherent algebras
• 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
• 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
• Solving Algorithmic Problems on Orders and Lattices by Relation Algebra and RelView
• scientific article; zbMATH DE number 4217898 (Why is no real title available?)
• Complexity of equations valid in algebras of relations. I: Strong non-finitizability
• The complexity of constraint satisfaction problems for small relation algebras
• scientific article; zbMATH DE number 1953891 (Why is no real title available?)
• Complexity of equational theory of relational algebras with standard projection elements

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)