Apakah masalah isomorfisma semigroup invers terbatas hingga GI selesai?

Apakah masalah isomorfisma semigroup invers terbatas hingga GI selesai ? Di sini semigroup invers terbatas diasumsikan diberikan oleh tabel perkaliannya.

Ya, masalah isomorfisme semigroup invers terbatas hingga GI selesai! Ini adalah akibat wajar dari

Teorema: Kisi isomorfisme adalah isomorfisme lengkap

dari bagian 7.2 Lattices and Poset in

Booth, Kellogg S .; Colbourn, CJ (1977), Masalah yang secara politis setara dengan grafik isomorfisme, Laporan Teknis CS-77-04, Departemen Ilmu Komputer, Universitas Waterloo.

karena kisi (semi-) juga merupakan semigroup terbalik (idempotent commutative).

Bukti teorema dari laporan teknis:

Itu sudah cukup untuk mewakili grafik secara unik sebagai kisi. Diberi grafik dengan n simpul dan tepi m , kami mendefinisikan kisi dengan elemen untuk setiap simpul, elemen untuk setiap tepi, dan dua elemen tambahan ' 0 ' dan ' 1 ' . Elemen ' 1 ' mendominasi semua yang lain ( supremum ), dan elemen ' 0 ' didominasi oleh semua elemen lain (yang paling ). Suatu tepi mendominasi dengan tepat simpul-simpul yang merupakan titik akhirnya. Hasilnya adalah kisi yang unik mewakili G .$G$$n$$m$$\text{'}0\text{'}$$\text{'}1\text{'}$$\text{'}1\text{'}$$\text{'}0\text{'}$$G$

Gagasan untuk jawaban ini berasal dari diskusi dengan vzn tentang pertanyaan yang cukup terfokus . Motivasi untuk menghabiskan waktu pada grafik isomorfisme sama sekali juga berasal dari dorongan berulang vzn. J.-E. Pin bertanya dalam komentar apakah ada alasan khusus untuk mempertimbangkan semigroup terbalik. Idenya adalah untuk memiliki struktur yang sedikit menggeneralisasi kelompok, yang merupakan GI lengkap. Saya ingin lebih memahami hubungan antara isomorfisme kelompok dan grafik isomorfisme, tetapi saya khawatir jawaban ini tidak memberikan wawasan semacam ini.