Enumeration of AC equivalent pairs

Below you can find a description of how to reproduce results described in D. Panteleev, A. Ushakov - Conjugacy search problems and the Andrews-Curtis conjecture. The actual programs used can be downloaded from https://github.com/dpantele/crag/tree/FoldedGraph/master and related branches (see below). There is a newer and better version at https://github.com/dpantele/acc, but currently it completely lacks documentatino and not all routines were reimplemented there.

Fast track

To reproduce results from the article (i.e. enumerate AC-equivalent pairs of the (xyxYXY, xxxYYYY) pair), execute the following commands. They are tested in Ubuntu Xenial, build prerequisites: sudo apt-get install cmake g++ git.

#!/bin/bash

# few parameters below
MAX_HL=13 # maximal harvest length
JOBS=$(grep -c ^processor /proc/cpuinfo) # number of parallel processes to use, # of cores by default

# this is defaulted as it was in the article
MAX_TL=$((2*$MAX_HL + 2))  # sanity restrictions because current version uses LEX order

# checking out source
mkdir crag-acc && cd crag-acc
git clone https://github.com/dpantele/crag.git src
cd src
git checkout FoldedGraph/master
cd ..

# building
cmake -Hsrc/ -B_build -DCMAKE_BUILD_TYPE=Release 
cmake --build _build --target FoldedGraphAccHarvest_main_main -- -j $JOBS

# running 
time _build/FoldedGraphAccHarvest/bin/main init:xyxYXY:xxxYYYY maxhl:$MAX_HL maxtl:$MAX_TL j:$JOBS out:h$MAX_HL &
tail -f h$MAX_HL.txt # exit with Ctrl+C after time was printed

# counting number of words - reproducing numbers from the table from the article
cat h${MAX_HL}_proc_words.txt | cut -f 2- -d, | tail -n +2 | awk '{print length($0) - 3;}' | sort | uniq -c

When process stops, h*_proc_words.txt contains a list of words which are equivalent to the original pair.

To reproduce a table from the article, first run the main program for all harvest lengths from 10 to 21 (but that would take weeks, so we propose that this is done for length 10..17):

JOBS=$(grep -c ^processor /proc/cpuinfo)
for HL in $(seq 10 17); do
    TL=$((2*$HL + 2))
    _build/FoldedGraphAccHarvest/bin/main init:xyxYXY:xxxYYYY maxhl:$HL maxtl:$TL j:$JOBS out:h$HL
    done

General information

Different branches of https://github.com/dpantele/crag/tree/FoldedGraph/BRANCH kind contain various versions of our programs. They share common build requirements and also general build instructions.

Build requirements

1. Linux OS. While in general routines are not os-specific, we have never tried to run the software on any kind of system but Ubuntu 14.04+.
2. Clang++/G++ with c++11 support. We recommend using gcc5+ or clang 3.6+
3. CMake 3.1.0+
4. (optional) Git source control system

How to build

This version of programs was implemented as a subpackage of the CRAG system, but actually does not depend on any other subpackages because all basic routines were replaced with an efficient implementation for the 2-letters case. Below are the instructions on only how to build programs in FoldedGraph2 and FoldedGraphAccHarvest modules:

• Obtain a copy of a source code, e.g.

mkdir crag-acc && cd crag-acc
git clone https://github.com/dpantele/crag.git src
cd src
git checkout FoldedGraph/master
cd ..

• Run CMake (read cmake documentation for details)

cmake -Hsrc/ -B_build -DCMAKE_BUILD_TYPE=Release

• Build the FoldedGraphAccHarvest module

cd _build/FoldedGraphAccHarvest/
make

• bin/ subdirectory will contain some programs, test/ will contain tests. See below for description of specific programs.

Description of branches content

TODO