jurina.ipynb

jurina.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOvGms3nWWLX1J1J2Wcf2Ec",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/james-d-mitchell/5b608eac0739b9d6fa2ea24cb9928603/jurina.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qh9A2P61E9GN",
        "outputId": "6e3bc64c-c730-404e-e142-d287089b61f7"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
            "Collecting libsemigroups_pybind11==0.4.3\n",
            "  Downloading libsemigroups_pybind11-0.4.3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (2.5 MB)\n",
            "\u001b[K     |████████████████████████████████| 2.5 MB 5.2 MB/s \n",
            "\u001b[?25hCollecting pybind11>=2.6\n",
            "  Downloading pybind11-2.10.1-py3-none-any.whl (216 kB)\n",
            "\u001b[K     |████████████████████████████████| 216 kB 52.7 MB/s \n",
            "\u001b[?25hCollecting pkgconfig>=1.5.0\n",
            "  Downloading pkgconfig-1.5.5-py3-none-any.whl (6.7 kB)\n",
            "Requirement already satisfied: packaging>=20.4 in /usr/local/lib/python3.7/dist-packages (from libsemigroups_pybind11==0.4.3) (21.3)\n",
            "Requirement already satisfied: pyparsing!=3.0.5,>=2.0.2 in /usr/local/lib/python3.7/dist-packages (from packaging>=20.4->libsemigroups_pybind11==0.4.3) (3.0.9)\n",
            "Installing collected packages: pybind11, pkgconfig, libsemigroups-pybind11\n",
            "Successfully installed libsemigroups-pybind11-0.4.3 pkgconfig-1.5.5 pybind11-2.10.1\n"
          ]
        }
      ],
      "source": [
        "!pip install libsemigroups_pybind11==\"0.4.3\""
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Some helper functions\n",
        "def inverse(u):\n",
        "  return \"\".join(reversed(u.swapcase()))\n",
        "\n",
        "def cyclic_perm(u, i):\n",
        "  return u[i:] + u[:i]\n",
        "\n",
        "def is_conjugate(k, u, v, conj):\n",
        "  u = inverse(u)\n",
        "  conj_inv = inverse(conj)\n",
        "  for i in range(len(v)):\n",
        "    vv = cyclic_perm(v, i)\n",
        "    if k.equal_to(conj + vv + conj_inv + u, \"\"):\n",
        "      return True, i\n",
        "  return False, None"
      ],
      "metadata": {
        "id": "ebit8XnZFAhN"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "from libsemigroups_pybind11 import KnuthBendix\n",
        "# yields the following which does terminate in approx. 500ms with 764 rules\n",
        "k = KnuthBendix()\n",
        "A = \"heicHJdIgCDaBGLkjFbfKlAE\"\n",
        "k.set_alphabet(A)\n",
        "k.set_identity(\"\")\n",
        "k.set_inverses(k.alphabet().swapcase())\n",
        "k.active_rules()\n",
        "k.add_rule(\"ajkhedc\", \"\")\n",
        "k.add_rule(\"EldhAfc\", \"\")\n",
        "k.add_rule(\"CFBiekA\", \"\")\n",
        "k.add_rule(\"agchbCD\", \"\")\n",
        "k.run()\n",
        "k.finished()\n",
        "k.number_of_active_rules()\n",
        "\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8geWWK9nFPUt",
        "outputId": "32a77437-5887-4d46-c9fd-17e52d29325f"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "764"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "is_conjugate(k, \"jkhldh\", \"CGKEIH\", \"jkheagc\"), is_conjugate(k, \"CGKEIH\", \"jkhldh\", \"jkheagc\"), is_conjugate(k, \"jkhldh\", \"CGKEIH\", inverse(\"jkheagc\")), is_conjugate(k, \"CGKEIH\", \"jkhldh\", inverse(\"jkheagc\"))\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WIAmdBmAFYDv",
        "outputId": "606538b5-bb41-40a2-92e9-dfeb876f93b8"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "((True, 0), (False, None), (False, None), (True, 0))"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "EO1e3YJFFn7n"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}