A boundary of isomorphism completeness in the lattice of semigroup pseudovarieties

1. L. Babai: Moderately exponential bound for graph isomorphism, FCT 81, Lecture Notes in Comp. Sci. 117, Springer 1981, 34–50.

   Google Scholar 

2. K. S. Booth: Isomorphism testing for graphs, semigroups and finite automata are polynomially equivalent problems, SIAM J. Comput. 7 (1978), 273–279.

   Article  MathSciNet  Google Scholar 

3. K. S. Booth, Ch. J. Colbourn: Problems polynomially equivalent to graph isomorphism, Tech. Rep. CS-77-04, Univ. of Waterloo, 1979.

   Google Scholar 

4. N. Christofides: Graph theory, an algorithmic approach, Acad. Press, New York, London, San Francisco, 1975.

   MATH  Google Scholar 

5. A. H. Clifford, G. B. Preston: The algebraic theory of semigroups, AMS, Providence, Rhode Island, 1967.

   MATH  Google Scholar 

6. L. Kučera, V. Trnková: Isomorphism completeness for some algebraic structures, FCT 81, Lecture Notes in Comp. Sci. 117, Springer 1981, 218–225.

   Google Scholar 

Download references