How much semigroup structure is needed to encode graphs ?

DOI10.1051/ita/1986200201911zbMath0601.20053MaRDI QIDQ3735947

A. Goralčíková, Václav Koubek, Pavel Goralčík

Publication date: 1986

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/1986200201911

zbMATH Keywords

isomorphism complete; critical varieties of finite semigroups; polynomial time isomorphism algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

08B15: Lattices of varieties

20M07: Varieties and pseudovarieties of semigroups

20M05: Free semigroups, generators and relations, word problems

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Minimal group-universal varieties of semigroups