# Design Technology Co-Optimization for Neuromorphic Computing

Ankita Paul, Shihao Song and Anup Das  Electrical and
Computer Engineering
Drexel University
Philadelphia, PA 19104
Email<EMAIL_ADDRESS>
###### Abstract

We present a design-technology tradeoff analysis in implementing machine-
learning inference on the processing cores of a Non-Volatile Memory
(NVM)-based many-core neuromorphic hardware. Through detailed circuit-level
simulations for scaled process technology nodes, we show the negative impact
of design scaling on read endurance of NVMs, which directly impacts their
inference lifetime. At a finer granularity, the inference lifetime of a core
depends on 1) the resistance state of synaptic weights programmed on the core
(design) and 2) the voltage variation inside the core that is introduced by
the parasitic components on current paths (technology). We show that such
design and technology characteristics can be incorporated in a design flow to
significantly improve the inference lifetime.

##  I Introduction

Neuromorphic systems are integrated circuits designed to mimic the
computations in a mammalian brain [1]. They enable energy-efficient execution
of Spiking Neural Networks (SNN) [2] and therefore, these systems are suitable
for implementing machine learning inference tasks for embedded Systems and
Edge devices in Internet-of-Things (IoT). A neuromorphic system consists of
processing cores that implement neurons and synapses. Multiple such cores are
interconnected together using Segmented Bus [3] or Network-on-Chip (NoC) [4]
to design a many-core neuromorphic hardware [5]. Table I illustrates the
neuron and synapse capacity of recent neuromorphic hardware cores.

TABLE I: Capacity of recent neuromorphic systems. | ODIN |  $\mathbf{\mu}$Brain | DYNAPs | BrainScaleS | SpiNNaker | Neurogrid | Loihi | TrueNorth
---|---|---|---|---|---|---|---|---
| [6] | [7] | [8] | [9] | [10] | [11] | [12] | [13]
# Neurons/core | 256 | 336 | 256 | 512 | 36K | 65K | 130K | 1M
# Synapses/core | 64K | 38K | 16K | 128K | 2.8M | 8M | 130M | 256M
# Cores/chip | 1 | 1 | 1 | 1 | 144 | 128 | 128 | 4096
# Chips/board | 1 | 1 | 4 | 352 | 56 | 16 | 768 | 4096
# Neurons | 256 | 336 | 1K | 4M | 2.5B | 1M | 100M | 4B
# Synapses | 256 | 336 | 65K | 1B | 200B | 16B | 100B | 1T

A neuromorphic core can be implemented using an analog crossbar where bitlines
and wordlines are organized in a grid with memory cells connected at their
crosspoints to store the synaptic weights [14, 15, 16, 17]. Neuron circuits
are implemented along bitlines and wordlines (see Figure 2). Recently, Non-
Volatile Memory (NVM) technologies such as phase-change memory (PCM) and
oxide-based resistive switching random access memory (OxRRAM) are used to
implement the memory cells in a neuromorphic core due to their low power
consumption, CMOS-compatible scaling, and multilevel analog operations
[18].111NVMs are also used in classical von Neumann computing to mitigate the
performance and energy bottlenect of DRAM [19, 20, 21, 22, 23, 24, 25]. In an
NVM-based neuromorphic inference hardware, the resistance state corresponding
to the synaptic weights of an SNN are programmed on the NVM cells.

Unfortunately, NVMs suffer from reliability issues such as circuit aging,
limited endurance, and read disturbance [26, 27, 28, 29]. Many of these issues
have been addressed recently in the context of neuromorphic computing [30, 31,
32, 33, 34, 35, 36, 37]. In this work, we focus on the read disturbance issues
of OxRRAM technology, where an OxRRAM cell’s resistance state may change after
performing a certain number of read operations [38, 39, 40]. Therefore, when
an OxRRAM-based neuromorphic hardware is used to implement an inference task,
the trained synaptic weights programmed on the hardware may change after
performing a few inference operations. To ensure expected results from an
inference task, the trained weights need to be reprogrammed on to the hardware
periodically. Reprogramming of synaptic weights to a neuromorphic hardware
involves offlining the hardware and transferring the weights from the host to
the hardware via a bandwidth-limited interconnect. This can significantly
increase the overhead, and lower the availability and reliability of
neuromorphic computing.

In this work, we present a design-technology tradeoff analysis in implementing
machine learning inference on many-core neuromorphic hardware. Through
circuit-level simulations we show the negative impact of design scaling on
read endurance of NVMs, which directly impacts their inference lifetime. We
show that the inference lifetime of a crossbar depends on 1) the resistance
state of synaptic weights programmed on the NVMs and 2) the voltage variation
inside the crossbar that is introduced by the parasitic components on current
paths. Such design and technology characteristics can be incorporated in a
design flow to significantly improve the inference lifetime.

##  II Background

We briefly introduce Spiking Neural Network (SNN) and their implementation in
hardware.

Spiking Neural Networks (SNNs) are the third generation of neural networks
designed using spiking neurons and bio-inspired learning algorithms [2]. In an
SNN, spikes injected from pre-synaptic neurons raise the membrane voltage of a
post-synaptic neuron (middle sub-figure of Figure 1). When the membrane
voltage crosses a threshold ($V_{\text{th}}$), the post-synaptic neuron emits
spikes that propagate to other neurons (right sub-figure of Figure 1). SNNs
implement some variants of Integrate and Fire (I&F) neurons with a spike
duration ranging from 1 $\mu$s to several ms [41, 42, 43] (left sub-figure of
Figure 1).

Figure 1: A leaky integrate-and-fire (LIF) neuron. The membrane potential over
time of the neuron (middle). The spike output of the neuron representing its
firing time (right).

SNNs can implement many machine learning approaches [44, 45, 46, 47, 48, 49,
50, 51]. In a supervised machine learning, an SNN is pre-trained with
representative data. Machine-learning inference refers to feeding live data
points to this trained SNN to generate the corresponding output. The quality
of machine learning inference can be expressed in terms of accuracy [48], Mean
Square Error (MSE) [44], Peak Signal-to-Noise Ratio (PSNR) [52], and
Structural Similarity Index Measure (SSIM) [53]. For SNNs, these quality
metrics are defined in terms of the inter-spike interval (ISI) [54, 55, 56,
57]. If $\\{t_{1},t_{2},\cdots,t_{K}\\}$ denote a neuron’s firing times in the
time interval $[0,T]$, the average ISI of this spike train is

$\footnotesize\mathcal{I}=\sum_{i=2}^{K}(t_{i}-t_{i-1})/(K-1).$ (1)

A neuromorphic hardware platform is implemented as a tiled architecture, where
tiles are interconnected via a time-multiplexed shared interconnect. Each tile
consists of a neuromorphic processing core, which can implement neurons and
synapses of a machine learning model. A common design practice is to use an
analog crossbar to implement a core.

In a crossbar, pre-synaptic neuron circuits are placed on horizontal wires
called wordlines, while post-synaptic neuron circuits are placed on vertical
wires called bitlines. Memory cells are placed at the crosspoint of each
wordline and bitline, and they implement the synaptic weights of an SNN. The
left subfigure of Figure 2 illustrates an $N\times N$ crossbar. The right
subfigure illustrates the parasitic RC components on the current path from a
pre-synaptic neuron to a post-synaptic neuron accessing the memory cell
$(i,j)$ located at the crosspoint of $i^{\text{th}}$ wordline and
$j^{\text{th}}$ bitline.

Figure 2: An $N\times N$ crossbar showing the parasitic components within.

Overall, a neuromorphic hardware enables distributed and pipelined processing
of SNN operations. Additionally, each crossbar in the hardware can implement a
maximum of $N$ pre-synaptic neurons per post-synaptic neuron. Therefore,
system-software frameworks such as NEUTRAMS [58], NeuroXplorer [59], Corelet
[60], PACMAN [61], and LAVA [62] consist of 1) a compiler, which partitions an
SNN model into clusters such that the neurons and synapses of each cluster can
be mapped to a crossbar of the hardware, and 2) a run-time manager, which maps
the clusters of an SNN to the cores of a many-core hardware. To this end,
several mapping strategies have been proposed, including optimizing for energy
[63, 64, 65, 66], throughput [67, 68, 69, 70], resource utilization [71, 72,
62, 58, 56], circuit aging [34, 31, 32, 30, 33], inference lifetime [39], and
write endurance [35, 36, 37]. These mapping techniques all use some variant of
the SNN-partitioning approach proposed in SpiNeMap [64].

Recently, dataflow models have been used to analyze performance of SNNs
implemented on neuromorphic hardware, especially using Synchronous Dataflow
Graphs (SDFGs) [73].222SDFGs are commonly used to model streaming applications
that are implemented on a multi-core system and their performance analysis
[74, 75, 76, 77, 78]. There are two strategies proposed in literature – the
SDFSNN [67] and its extended versions [68, 79, 80], which uses dataflow graphs
to model an SNN, performing partitioning and mapping explorations with neurons
and synapses directly, and the DFSynthesizer [69] and its extended version
[70], which uses dataflow graphs to only model the clustered SNN, allowing
mapping and scheduling of the clusters (a collection of neurons and synapses)
to the PEs of a neuromorphic hardware.

Emerging non-volatile memory (NVM) technologies such as phase-change memory
(PCM), oxide-based memory (OxRAM), spin-based magnetic memory (STT-MRAM), and
Flash have recently been used for synaptic storage in crossbars. NVMs are non-
volatile, have high CMOS compatibility, and can achieve high integration
density. Each NVM device can implement both a single-bit and multi-bit
synapse. Because of these properties, an NVM-based neuromorphic hardware
typically consumes energy that is magnitudes lower than using SRAMs [81, 82,
83]. However, NVMs also introduce reliability issues [26]. Table II summarizes
them for different NVMs.

TABLE II: Reliability issues in NVMs. Reliability Issues | NVMs
---|---
High-voltage related circuit aging | PCM, Flash
High-current related circuit aging | OxRAM, STT-MRAM
Limited read endurance | All
Limited write endurance | All

We discuss one specific issue – limited read endurance for OxRRAM-based
neuromorphic hardware.

##  III Introduction to Oxide-based Resistive RAM

The resistance switching random access memory (OxRRAM) technology presents an
attractive option for implementing the synaptic cells of a crossbar due to its
demonstrated potential for low-power multi-level operation and high
integration density [18]. An OxRRAM cell is composed of an insulating film
sandwiched between conducting electrodes forming a metal-insulator-metal (MIM)
structure (see Figure 3). Recently, filament-based metal-oxide OxRRAM
implemented with transition-metal-oxides such as HfO2, ZrO2, and TiO2 has
received considerable attention due to their low-power and CMOS-compatible
scaling.

Figure 3: Operation of an OxRRAM cell with the $\text{HfO}_{2}$ layer
sandwiched between the metals Ti (top electrode) and TiN (bottom electrode).
The left subfigure shows the formation of LRS states with the formation of
conducting filament (CF). This represents logic states 01, 10, and 11. The
right subfigure shows the depletion of CF on application of a negative voltage
on the TE. This represents the HRS state or logic 00.

Synaptic weights are represented as conductance of the insulating layer within
each OxRRAM cell. To program an OxRRAM cell, elevated voltages are applied at
the top and bottom electrodes, which re-arranges the atomic structure of the
insulating layer. Figure 3 shows the High-Resistance State (HRS) and the Low-
Resistance State (LRS) of an OxRRAM cell. An OxRRAM cell can also be
programmed into intermediate low-resistance states, allowing its multilevel
operations.

In OxRRAM technology, the transition from HRS state is governed by a sudden
decrease of the vertical filament gap on application of stress voltage during
spike propagation [38]. This is illustrated in the left subfigure of Figure 4
where the vertical filament gap is shown to reduce by an amount $h$. This may
result in a conducting filament between the two metal layers causing the
resistive state to change from HRS to LRS. The rate of change of the filament
gap of the OxRRAM cell at the $(i,j)^{\text{th}}$ location in the crossbar is

$\footnotesize\frac{dg_{i,j}}{dt}=-\vartheta_{0}\cdot
e^{-\frac{E_{a}}{kT}}sinh\left(\frac{\gamma_{i,j}\cdot
a_{0}}{L}\cdot\frac{qV_{i,j}}{kT}\right)\text{, where
}\gamma_{i,j}=\gamma_{0}-\beta\cdot\frac{g_{i,j}}{g_{0}}^{3}$ (2)

In the above equation, $t$ defines the state transition time, $g_{0}$ is the
initial filament gap of the OxRRAM cell, $V_{i,j}$ is the voltage applied to
the cell, $\gamma_{i,j}$ is the local field enhancement factor and is related
to the gap $g_{i,j}$, $a_{0}$ is the atomic hoping distance, and $\gamma_{0}$
is a fitting constant.

The transition from one of the LRS states is governed by the lateral filament
growth [38]. This is illustrated in the right subfigure of Figure 4. The time
for state transition in the $(i,j)^{\text{th}}$ RRAM cell is given by

$\footnotesize t_{i,j}(LRS)=10^{-14.7\cdot V_{i,j}+6.7}\text{sec}$ (3)

Figure 4: Read disturbances due to structural alteration in an OxRRAM cell.
The left subfigure shows a reduction of the conductive filament gap on
application of a stress voltage. Such changes leads to a reduction in the
resistance, i.e., a read disturbance of HRS state in the cell. The right
subfigure shows the lateral growth of the conductive filament due to
application of a stress voltage. This illustrates read disturbance of LRS
state in the cell.

If the state transition time of an OxRRAM cell is 1000 ms, then a single
quasi-static read operating using 1000 ms read pulse or 1000 read accesses
using with 1-ms spike pulses can lead to an abrupt change in the state of the
cell. Therefore, the endurance of the cell is 1000. If the cell propagates $n$
spikes during inference of each image, then the inference lifetime is defined
as $1000/n$. Formally,

$\footnotesize\text{inference lifetime}=\frac{\text{read
endurance}}{\text{spikes per image}}$ (4)

##  IV Design-Technology Tradeoff Analysis

The computer memory industry has thus far been primarily driven by the cost-
per-bit metric, which provides the maximum capacity for a given manufacturing
cost. As shown in recent works [22, 21, 84, 19, 20, 23, 24], manufacturing
cost can be estimated from the area overhead. To estimate the cost-per-bit of
a neuromorphic core, we investigate the internal architecture of a crossbar
and find that a neuron circuit can be designed using 20 transistors and a
capacitor [85], while an NVM cell is a 1T-1R arrangement with a transistor
used as an access device for the cell. Within an $N\times N$ crossbar, there
are $N$ pre-synaptic neurons, $N$ post-synaptic neurons, and $N^{2}$ synaptic
cells. The total area of all the neurons and synapses of a crossbar is

neuron area $\displaystyle=2N(20T+1C)$ synapse area
$\displaystyle=N^{2}(1T+1R)$

where $T$ stands for transistor, $C$ for capacitor, and $R$ for NVM cell. The
total synaptic cell capacity is $N^{2}$, with each NVM cell implementing 2-bit
per synapse. The total number of bits (i.e., synaptic capacity) in the
crossbar is

$\footnotesize\text{total bits}=2N^{2}$ (6)

Therefore, the cost-per-bit of an $N$x$N$ crossbar is

$\footnotesize\text{cost-per-
bit}=\frac{2N(20T+1C)+N^{2}(1T+1R)}{2N^{2}}\approx\frac{F^{2}(27+2N)}{N},$ (7)

where the cost-per-bit is represented in terms of the crossbar dimension $N$
and the feature size $F$. Equation 7 provides a back-of-the-envelope
calculation of cost-per-bit. Figure 5 plots the normalized cost-per-bit for
four different process technology nodes, with the crossbar dimension ranging
from 16 to 256. We observe that the cost-per-bit reduces with increase in the
dimension of a crossbar, i.e., larger-sized crossbars can accommodate more
bits for a given cost.

Figure 5: Cost-per-bit analysis of a crossbar.

We now analyze the internal architecture of a crossbar. Figure 6a shows the
current through the memory cells in a 128x128 crossbar. This current variation
is due to the difference in the length of current paths from pre to post-
synaptic neurons in the crossbar, where the length of a current path is
measured in terms of the number of parasitic components on the path. These
current values are obtained for a 65nm technology node and at 300K temperature
corner. As can be clearly seen from the figure, current through memory cells
on the top-right corner of the crossbar is lower than those at the bottom-left
corner.

(a) Current map in a 128x128 crossbar. (b) RRAM endurance in a 128x128
crossbar.

Figure 6: Current map and RRAM endurance in a 128x128 crossbar.

Figure 6b shows the endurance variation of a 128x128 crossbar at 45 nm node
and at 30∘C with each RRAM cell programmed to HRS state. The endurance
variation is a direct result of the current variation in the crossbar.

Figure 7 shows the difference between currents on the shortest and longest
paths for 32x32, 64x64, 128x128, and 256x256 crossbars at 65nm process node.
The input spike voltage of the pre-synaptic neurons is set to generate $50\mu
A$ on the longest path. This current value corresponds to the current needed
to read the resistance state of an OxRRAM cell.

Figure 7: Difference between current on the shortest and the longest path for
different crossbar sizes.

We observe that the current injected into the post-synaptic neuron on the
longest path is lower than the current on the shortest path by 13.3% for
32x32, 25.1% for 64x64, 39.2% for 128x128, and 55.8% for 256x256 crossbar.
This current difference is because of the higher voltage drop on the longest
path, which reduces the current on this path compared to the shortest path for
the same amount of spike voltage applied on both these paths. The current
difference increases with crossbar size because of the increase in the number
of parasitic resistances on the longest current path, which results in larger
voltage drops, lowering the current injected into its post-synaptic neuron.
However, larger current variation causes larger endurance variation as
illustrated in Figure 6b. Therefore, larger crossbar sizes leads to larger
endurance variation.

System designers often make a tradeoff between cost-per-bit and endurance
variation. Typically, crossbar sizes of $128\times 128$ and $256\times 256$
gives the best tradeoff.

##  V Design Flow Incorporating
Design-Technology Tradeoff

An optimized design flow is one, which takes into account the design and
technology characteristics to place neurons and synapses to a crossbar such
that those synapses that propagate more spikes are mapped to NVMs with higher
read endurance. This is to increase the inference lifetime.

In our prior work [39], we show that such a design flow can significantly
improve the inference lifetime. Figure 8 reports the inference lifetime for 10
applications for the proposed design flow normalized to SpiNeMap. We observe
that through intelligent synapse mapping, the inference lifetime obtained
using the proposed approach is on average 3.4x higher.

Figure 8: Inference lifetime normalized to SpiNeMap.

##  VI Conclusion

A design-technology tradeoff analysis is performed to investigate inference
lifetime of neuromorphic hardware that adopts NVM as synaptic storage. An
essential observation of the analysis is that the read endurance of an NVM
cell depends on its programmed synaptic weight (design) and the voltage
exposed to the cell (technology). Our analysis also reveals that voltages
exposed to NVM cells inside a crossbar vary due to the parasitic components on
current paths, which leads to asymmetric read endurance across NVM cells in a
crossbar. From detailed circuit-level simulations, we show design scaling on
read endurance of NVMs negatively impacts the inference lifetime of
neuromorphic hardware. In addition, the design flow that considers asymmetry
in read endurance can significantly improve the inference lifetime of
neuromorphic hardware.

## Acknowledgment

This work is supported by the United States National Science Foundation
Faculty Early Career Development Award CCF-1942697 (CAREER: Facilitating
Dependable Neuromorphic Computing: Vision, Architecture, and Impact on
Programmability) and the United States Department of Energy CAREER Award DE-
SC0022014 (Architecting the Hardware-Software Interface for Neuromorphic
Computers).

## References

  * [1] C. Mead, “Neuromorphic electronic systems,” _Proc. of the IEEE_ , 1990.
  * [2] W. Maass, “Networks of spiking neurons: The third generation of neural network models,” _Neural Networks_ , 1997.
  * [3] A. Balaji _et al._ , “Exploration of segmented bus as scalable global interconnect for neuromorphic computing,” in _GLSVLSI_ , 2019.
  * [4] X. Liu _et al._ , “Neu-NoC: A high-efficient interconnection network for accelerated neuromorphic systems,” in _ASP-DAC_ , 2018.
  * [5] F. Catthoor _et al._ , “Very large-scale neuromorphic systems for biological signal processing,” in _CMOS Circuits for Biological Sensing and Processing_ , 2018.
  * [6] C. Frenkel _et al._ , “A 0.086-mm2 12.7-pj/sop 64k-synapse 256-neuron online-learning digital spiking neuromorphic processor in 28-nm CMOS,” _TBCAS_ , 2018.
  * [7] J. Stuijt _et al._ , “$\mu$Brain: An event-driven and fully synthesizable architecture for spiking neural networks,” _Frontiers in Neuroscience_ , 2021.
  * [8] S. Moradi _et al._ , “A scalable multicore architecture with heterogeneous memory structures for dynamic neuromorphic asynchronous processors (DYNAPs),” _TBCAS_ , 2017.
  * [9] J. Schemmel _et al._ , “Live demonstration: A scaled-down version of the brainscales wafer-scale neuromorphic system,” in _ISCAS_ , 2012.
  * [10] S. Furber _et al._ , “The SpiNNaker project,” _Proc. of the IEEE_ , 2014\.
  * [11] B. Benjamin _et al._ , “Neurogrid: A mixed-analog-digital multichip system for large-scale neural simulations,” _Proceedings of the IEEE_ , 2014.
  * [12] M. Davies _et al._ , “Loihi: A neuromorphic manycore processor with on-chip learning,” _IEEE Micro_ , 2018.
  * [13] M. V. Debole _et al._ , “TrueNorth: Accelerating from zero to 64 million neurons in 10 years,” _Computer_ , 2019.
  * [14] C. Liu _et al._ , “A spiking neuromorphic design with resistive crossbar,” in _DAC_ , 2015.
  * [15] M. Hu _et al._ , “Memristor crossbar-based neuromorphic computing system: A case study,” _TNNLS_ , 2014.
  * [16] M. Hu _et al._ , “Dot-product engine for neuromorphic computing: Programming 1T1M crossbar to accelerate matrix-vector multiplication,” in _DAC_ , 2016.
  * [17] A. Ankit _et al._ , “TraNNsformer: Neural network transformation for memristive crossbar based neuromorphic system design,” in _ICCAD_ , 2017\.
  * [18] A. Mallik _et al._ , “Design-technology co-optimization for OxRRAM-based synaptic processing unit,” in _VLSIT_ , 2017.
  * [19] S. Song _et al._ , “Enabling and exploiting partition-level parallelism (PALP) in phase change memories,” _TECS_ , 2019.
  * [20] O. Mutlu, “Memory scaling: A systems architecture perspective,” in _IMW_ , 2013.
  * [21] S. Song _et al._ , “Improving phase change memory performance with data content aware access,” in _ISMM_ , 2020.
  * [22] O. Mutlu _et al._ , “Research problems and opportunities in memory systems,” _SUFI_ , 2015.
  * [23] S. Song _et al._ , “Exploiting inter- and intra-memory asymmetries for data mapping in hybrid tiered-memories,” in _ISMM_ , 2020.
  * [24] S. Song _et al._ , “Aging-aware request scheduling for non-volatile main memory,” in _ASP-DAC_ , 2021.
  * [25] S. Song _et al._ , “Design methodologies for reliable and energy-efficient PCM systems,” in _IGSC Workshops_ , 2020.
  * [26] R. M. Shelby _et al._ , “Non-volatile memory as hardware synapse in neuromorphic computing: A first look at reliability issues,” in _IRPS_ , 2015\.
  * [27] L. Larcher _et al._ , “High-$\kappa$ related reliability issues in advanced non-volatile memories,” _Microelectronics Reliability_ , 2010.
  * [28] C.-Y. Lu _et al._ , “Non-volatile memory technology-today and tomorrow,” in _IPFA_ , 2006.
  * [29] P. Noé _et al._ , “Phase-change materials for non-volatile memory devices: from technological challenges to materials science issues,” _Semiconductor Science and Technology_ , 2017.
  * [30] S. Song _et al._ , “A case for lifetime reliability-aware neuromorphic computing,” in _MWSCAS_ , 2020.
  * [31] A. Balaji _et al._ , “A framework to explore workload-specific performance and lifetime trade-offs in neuromorphic computing,” _CAL_ , 2019.
  * [32] S. Song _et al._ , “Improving dependability of neuromorphic computing with non-volatile memory,” in _EDCC_ , 2020.
  * [33] S. Kundu _et al._ , “Special session: Reliability analysis for ML/AI hardware,” in _VTS_ , 2021.
  * [34] S. Song _et al._ , “Dynamic reliability management in neuromorphic computing,” _JETC_ , 2021.
  * [35] T. Titirsha _et al._ , “Reliability-performance trade-offs in neuromorphic computing,” in _IGSC Workshops_ , 2020.
  * [36] T. Titirsha _et al._ , “Thermal-aware compilation of spiking neural networks to neuromorphic hardware,” in _LCPC_ , 2020.
  * [37] T. Titirsha _et al._ , “Endurance-aware mapping of spiking neural networks to neuromorphic hardware,” _TPDS_ , 2021.
  * [38] W. Shim _et al._ , “Impact of read disturb on multilevel RRAM based inference engine: Experiments and model prediction,” in _IRPS_ , 2020.
  * [39] S. Song _et al._ , “Improving inference lifetime of neuromorphic systems via intelligent synapse mapping,” in _ASAP_ , 2021.
  * [40] K.-T. Chen _et al._ , “Non-volatile ferroelectric FETs using 5-nm Hf 0.5 Zr 0.5 O 2 with high data retention and read endurance for 1T memory applications,” _EDL_ , 2019.
  * [41] S. Fusi _et al._ , “Collective behavior of networks with linear (VLSI) integrate-and-fire neurons,” _Neural Computation_ , 1999.
  * [42] S. Zhang _et al._ , “A pulse-width modulation neuron with continuous activation for processing-in-memory engines,” in _DATE_. IEEE, 2020.
  * [43] A. J. Leigh _et al._ , “An efficient spiking neuron hardware system based on the hardware-oriented modified Izhikevich neuron (HOMIN) model,” _TCAS II: Express Briefs_ , 2020.
  * [44] A. Das _et al._ , “Unsupervised heart-rate estimation in wearables with Liquid states and a probabilistic readout,” _Neural Networks_ , 2018.
  * [45] E. J. Moyer _et al._ , “Machine learning applications to DNA subsequence and restriction site analysis,” in _SPMB_ , 2020.
  * [46] J. P. Dominguez-Morales _et al._ , “Deep spiking neural network model for time-variant signals classification: a real-time speech recognition approach,” in _IJCNN_ , 2018.
  * [47] A. Das _et al._ , “Heartbeat classification in wearables using multi-layer perceptron and time-frequency joint distribution of ECG,” in _CHASE_ , 2018\.
  * [48] A. Balaji _et al._ , “Power-accuracy trade-offs for heartbeat classification on neural networks hardware,” _JOLPE_ , 2018.
  * [49] Q. Yu _et al._ , “A spiking neural network system for robust sequence recognition,” _TNNLS_ , 2015.
  * [50] S. Schliebs _et al._ , “Evolving spiking neural network—a survey,” _Evolving Systems_ , 2013.
  * [51] M. Dong _et al._ , “Unsupervised speech recognition through spike-timing-dependent plasticity in a convolutional spiking neural network,” _PloS one_ , 2018.
  * [52] T. Chou _et al._ , “CARLsim 4: An open source library for large scale, biologically detailed spiking neural network simulation using heterogeneous clusters,” in _IJCNN_ , 2018.
  * [53] A. Hore _et al._ , “Image quality metrics: PSNR vs. SSIM,” in _ICPR_ , 2010.
  * [54] P. A. Cariani, “Temporal coding of sensory information in the brain,” _Acoustical Science and Technology_ , 2001.
  * [55] H. Fang _et al._ , “Encoding, model, and architecture: systematic optimization for spiking neural network in FPGAs,” in _ICCAD_ , 2020.
  * [56] A. Balaji _et al._ , “PyCARL: A PyNN interface for hardware-software co-simulation of spiking neural network,” in _IJCNN_ , 2020.
  * [57] M. Kiselev, “Rate coding vs. temporal coding-is optimum between?” in _IJCNN_ , 2016.
  * [58] Y. Ji _et al._ , “NEUTRAMS: Neural network transformation and co-design under neuromorphic hardware constraints,” in _MICRO_ , 2016.
  * [59] A. Balaji _et al._ , “NeuroXplorer 1.0: An extensible framework for architectural exploration with spiking neural networks,” in _ICONS_ , 2021\.
  * [60] A. Amir _et al._ , “Cognitive computing programming paradigm: a corelet language for composing networks of neurosynaptic cores,” in _IJCNN_ , 2013\.
  * [61] F. Galluppi _et al._ , “A hierachical configuration system for a massively parallel neural hardware platform,” in _CF_ , 2012.
  * [62] C.-K. Lin _et al._ , “Mapping spiking neural networks onto a manycore neuromorphic architecture,” in _PLDI_ , 2018.
  * [63] A. Das _et al._ , “Mapping of local and global synapses on spiking neuromorphic hardware,” in _DATE_ , 2018.
  * [64] A. Balaji _et al._ , “Mapping spiking neural networks to neuromorphic hardware,” _TVLSI_ , 2020.
  * [65] T. Titirsha _et al._ , “On the role of system software in energy management of neuromorphic computing,” in _CF_ , 2021.
  * [66] A. Balaji _et al._ , “Run-time mapping of spiking neural networks to neuromorphic hardware,” _JSPS_ , 2020.
  * [67] A. Das _et al._ , “Dataflow-based mapping of spiking neural networks on neuromorphic hardware,” in _GLSVLSI_ , 2018.
  * [68] A. Balaji _et al._ , “A framework for the analysis of throughput-constraints of SNNs on neuromorphic hardware,” in _ISVLSI_ , 2019.
  * [69] S. Song _et al._ , “Compiling spiking neural networks to neuromorphic hardware,” in _LCTES_ , 2020.
  * [70] S. Song _et al._ , “DFSynthesizer: Dataflow-based synthesis of spiking neural networks to neuromorphic hardware,” _TECS_ , 2021.
  * [71] A. Balaji _et al._ , “Enabling resource-aware mapping of spiking neural networks via spatial decomposition,” _ESL_ , 2020.
  * [72] A. Balaji _et al._ , “Compiling spiking neural networks to mitigate neuromorphic hardware constraints”,” in _IGSC Workshops_ , 2020.
  * [73] E. Lee _et al._ , “Synchronous data flow,” _Proceedings of the IEEE_ , 1987.
  * [74] S. Sriram _et al._ , _Embedded Multiprocessors; Scheduling and Synchronization_ , 2000.
  * [75] L. Jiashu _et al._ , “A design flow for partially reconfigurable heterogeneous multi-processor platforms,” in _RSP_ , 2012.
  * [76] A. Das _et al._ , _Reliable and Energy Efficient Streaming Multiprocessor Systems_. Springer, 2018\.
  * [77] A. Das _et al._ , “Reliability and energy-aware mapping and scheduling of multimedia applications on multiprocessor systems,” _TPDS_ , 2015.
  * [78] A. H. Ghamarian _et al._ , “Throughput analysis of synchronous data flow graphs,” in _ACSD_ , 2006.
  * [79] S. Song _et al._ , “A design flow for mapping spiking neural networks to many-core neuromorphic hardware,” in _ICCAD_ , 2021.
  * [80] S. Curzel _et al._ , “Automated generation of integrated digital and spiking neuromorphic machine learning accelerators,” in _ICCAD_ , 2021.
  * [81] G. W. Burr _et al._ , “Neuromorphic computing using non-volatile memory,” _Advances in Physics: X_ , 2017.
  * [82] S. Kim _et al._ , “NVM neuromorphic core with 64k-cell (256-by-256) phase change memory synaptic array with on-chip neuron circuits for continuous in-situ learning,” in _IEDM_ , 2015.
  * [83] S. B. Eryilmaz _et al._ , “Device and system level design considerations for analog-non-volatile-memory based neuromorphic architectures,” in _IEDM_ , 2015.
  * [84] D. Lee _et al._ , “Tiered-latency DRAM: A low latency and low cost DRAM architecture,” in _HPCA_ , 2013.
  * [85] G. Indiveri, “A low-power adaptive integrate-and-fire neuron circuit,” in _ISCAS_ , 2003.


# Knots, Braids and First Order Logic

Siddhartha Gadgil  Department of Mathematics,
Indian Institute of Science,
Bangalore 560012, India<EMAIL_ADDRESS>and  Prathamesh, T . V . H

###### Abstract.

Determining when two _knots_ are equivalent (more precisely _isotopic_) is a
fundamental problem in topology. Here we formulate this problem in terms of
_Predicate Calculus_ , using the formulation of knots in terms of braids and
some basic topological results.

Concretely, Knot theory is formulated in terms of a language with signature
$(\cdot,T,\equiv,1,\sigma,\bar{\sigma})$, with $\cdot$ a $2$-function, $T$ a
$1$-function, $\equiv$ a $2$-predicate and $1$, $\sigma$ and $\bar{\sigma}$
constants. We describe a _finite_ set of axioms making the language into a
(first order) theory. We show that every knot can be represented by a term $b$
in $1$, $\sigma$, $\bar{\sigma}$ and $T$, and knots represented by terms
$b_{1}$ and $b_{2}$ are equivalent if and only if $b_{1}\equiv b_{2}$.

Our formulation gives a rich class of problems in First Order Logic that are
important in Mathematics.

###### 1991 Mathematics Subject Classification:

Primary 57M99; Secondary 17B99

##  1\. Introduction

A (tame) _knot_ is a _smooth embedding_ of the circle $S^{1}$ into
$3$-dimensional Euclidean space $\mathbb{R}^{3}$, or equivalently the
$3$-sphere $S^{3}$ (which is viewed as $\mathbb{R}^{3}$ with an additional
point at infinity). We say that two knots are _isotopic_ if one can be
deformed into the other through smooth embeddings (we give a more precise
definition in Section 2. Determining when two knots are equivalent is a
fundamental problem in topology.

The goal of this paper is to translate this topological problem into a problem
in predicate calculus. We shall in fact formulate the problem of _stable
equivalence of links_ , which generalises knot equivalence, in terms of
predicate calculus. Our formulation is based on the representation of knots in
terms of braids.

We give the definitions on knots, links and stable equivalence in Section 2.
We then state the axiom system for stable equivalence of links in Section 3.
We then recall the formulation of knot theory in algebraic terms via Braids in
Section 4. We reformulate this to give a concise description of stable
equivalence of links in Section 5. This allows us to prove that our axiom
system describes knot theory in Section 6. Finally, we give the topological
background concerning braids and knots in an Appendix (the paper can be read
without this).

##  2\. Knots, Links and stable equivalence

We begin by recalling some basic definitions. We shall assume that all knots
and links are smooth to exclude _wild knots_.

######  Definition 2.1.

A knot K is defined as the image of a smooth, injective map
$h:S^{1}\rightarrow S^{3}$ so that $h^{\prime}(\theta)\neq 0$ for all
$\theta\in S^{1}$.

######  Definition 2.2.

A link $L\subset S^{3}$ is a smooth 1-dimensional submanifold of $S^{3}$ such
that each component of $L$ is a knot and there are only finitely many
components.

We shall regard two links as the same if there is an _ambient isotopy_ between
them, which is defined as follows.

######  Definition 2.3 (Ambient Isotopy).

Two links $L_{1}$ and $L_{2}$ in $S^{3}$ are said to be ambient isotopic if
there exists a smooth map $F:S^{3}\times[0,1]\rightarrow S^{3}$ such that

  1. (1)

$F|_{{S^{3}}\times\\{0\\}}$ = $id|_{S^{3}}:S^{3}\rightarrow S^{3}$.

  2. (2)

$F|_{S^{3}\times\\{1\\}}(L_{1})=L_{2}$.

  3. (3)

$F|_{S^{3}\times\\{1\\}}$ is a diffeomorphism $\forall s\in[0,1]$.

  4. (4)

F is smooth.

This gives an equivalence relation by the following well-known theorem.

######  Theorem 2.4.

Ambient Isotopy induces an equivalent relation on the set of all links.

To give a description of knot theory in terms of predicate calculus, we
introduce another equivalence relation on links which we call _stable
equivalence_.

######  Definition 2.5.

A link $L^{\prime}$ is said to be a stabilisation of a link $L$ if the
following conditions hold.

  1. (1)

$L^{\prime}=L\cup L^{\prime\prime}$ with $L^{\prime\prime}$ disjoint from $L$.

  2. (2)

There is a collection $\\{D_{1},D_{2},\dots,D_{n}\\}$ of disjoint, smoothly
embedded discs in $S^{3}\setminus L$ with
$L^{\prime\prime}=\bigcup\limits_{i=1}^{n}\partial D_{i}$.

######  Definition 2.6.

Two links $L_{1}$ and $L_{2}$ are said to be stably equivalent, denoted
$L_{1}\equiv L_{2}$, if there are stabilisations $L^{\prime}_{1}$ and
$L^{\prime}_{2}$ of $L_{1}$ and $L_{2}$, respectively, that are ambient
isotopic.

It is easy to see that $\equiv$ is an equivalence relation. The following
result follows from the prime decomposition theorem of Knesser-Milnor (see,
for example, [3]).

######  Theorem 2.7.

If $K_{1}$ and $K_{2}$ are knots (regarded as links), then $K_{1}\equiv K_{2}$
if and only if $K_{1}$ is ambient isotopic to $K_{2}$.

We shall denote by $\mathcal{L}$ the set of equivalence classes of links up to
stable equivalence and by $\widetilde{\mathcal{L}}$ the set of ambient isotopy
classes of links. Thus $\mathcal{L}$ is a quotient of
$\widetilde{\mathcal{L}}$.

##  3\. Axioms in First Order Logic

In this section, we list a set of axioms which enable us to describe stable
equivalence of links in terms of first order logic with equality. In later
sections we will further substantiate on why these axioms suffice. Consider a
language with signature $(\cdot,T,\equiv,1,\sigma,\bar{\sigma})$ such that
$\cdot$ is a $2$-function , T is a $1$-function, $\equiv$ is a $2$-predicate,
while $1$, $\sigma$ and $\bar{\sigma}$ are constants. The system of axioms for
the infinite braid group in this language are the following.

  * •

Group Axioms (for the set of closed terms)

    1. (1)

$\forall x,y,z\quad(x\cdot(y\cdot z)=((x\cdot y)\cdot z)$

    2. (2)

$\forall x\quad 1\cdot x=x$

    3. (3)

$\forall x\quad x\cdot 1=x$

    4. (4)

$\sigma\cdot\bar{\sigma}=\bar{\sigma}\cdot\sigma=1$

  * •

Shift operation

    1. (1)

$\forall x,y\quad T(x\cdot y)=T(x)\cdot T(y)$

    2. (2)

$T(e)=e$

  * •

Braid axioms

    1. (1)

$\sigma\cdot T(\sigma)\cdot\sigma=T(\sigma)\cdot\sigma\cdot T(\sigma)$

    2. (2)

$\forall b\quad\sigma\cdot T^{2}(b)=T^{2}(b)\cdot\sigma$

  * •

Equivalence relation

    1. (1)

$\forall x\quad x\equiv x$

    2. (2)

$\forall x,y\quad x\equiv y\implies y\equiv x$

    3. (3)

$\forall x,y,z\quad x\equiv y\wedge y\equiv z\implies x\equiv z$

  * •

Markov moves

    1. (1)

$\forall x,y,z\quad y\cdot z=1\implies x\equiv y\cdot x\cdot z$

    2. (2)

$\forall x\quad x\equiv\sigma\cdot T(x)$

    3. (3)

$\forall x\quad x\equiv\bar{\sigma}\cdot T(x)$

Any model of these axioms will be referred to as a  link model and the axioms
will be referred to as link axioms.

##  4\. Algebraic Formulation of knot theory

In this section, we recall the algebraic formulation of knots in terms of
Braids. We first recall the definition of braid groups.

######  Definition 4.1.

The braid group $B_{n}$ is the group generated by
$\sigma_{1},\sigma_{2},\dots,\sigma_{n-1}$ with the relations

  1. (1)

$\sigma_{i}\cdot\sigma_{j}=\sigma_{j}\cdot\sigma_{i}$, where $1\leq i,j\leq
n-1$, $i\geq j+2$.

  2. (2)

$\sigma_{i}\cdot\sigma_{i+1}\cdot\sigma_{i}=\sigma_{i+1}\cdot\sigma_{i}\cdot\sigma_{i+1}$,
where $1\leq i\leq n-2$.

Note that for $m<n$, there is a natural inclusion homomorphism $i_{m}$ from
$B_{m}$ to $B_{n}$ mapping a generator $\sigma_{i}$ of $B_{m}$ to the
generator $\sigma_{i}$ of $B_{n}$. We can thus identify elements in $B_{m}$
with elements in $B_{n}$. From now we shall refer to elements of
$\bigcup_{n\in\mathbb{N}\setminus{\\{1\\}}}B_{n}$ as braids.

Given an integer $m>1$, we associate a diagram to every generator of the braid
group $B_{m}$, as in the following diagram.

One can thus associate a diagram to every element of $B_{m}$ by defining the
diagram associated to the product of two elements as in the figure below

Given an integer $m>1$ and a braid $b\in B_{m}$, we can associate to the braid
a link $\lambda(b,m)$ by closing up the diagram associated to a braid and
smoothening the sharp edges. A more rigorous construction is provided in the
Appendix Appendix: Topological background

This gives a function $\lambda:\mathcal{B}\to\widetilde{\mathcal{L}}$ from the
set

$\mathcal{B}=\\{(b,m):b\in B_{m}\\}$

to the set of links. The following result says that all links are obtained by
this construction.

######  Theorem 4.2 (Alexander).

For every link $L$, there is an integer $m>1$ and a braid $B\in B_{m}$ so that
$L$ is ambient isotopic to $\lambda(b,m)$.

######  Remark 4.3.

For $n>m$ and $b\in B_{m}\subset B_{n}$, $\lambda(b,m)$ is not ambient
isotopic to $\lambda(b,n)$. However it is easy to see that the links are
stably equivalent.

The following lemma is immediate from the fact that a braid
$\prod_{k=1}^{m}\sigma_{i_{k}}^{\epsilon_{k}}\in B_{n}$, where $\epsilon_{k}$
is $1$ or $-1$ and $i_{k}\in\mathbb{N}$, when viewed from the other side of
the plane in which the braid lies is represented by
$\prod_{k=1}^{m}\sigma_{n-i_{k}}^{\epsilon_{k}}$.

######  Lemma 4.4.

The braid elements $\prod_{k=1}^{m}\sigma_{i_{k}}^{\epsilon_{k}}$ and
$\prod_{k=1}^{m}\sigma_{n-i_{k}}^{\epsilon_{k}}$ are associated to the same
link.

To formulate knot theory in terms of braids, we also need to know when two
braids correspond to the same link. To state the result of Markov giving such
a characterisation, consider the equivalence relation $\sim$ on the set
$\mathcal{B}$ generated by

  * •

For $a,b\in B_{m}$, $(b,m)\sim(aba^{-1},m)$.

  * •

For $b\in B_{m}$, $(b,m)\sim(\sigma_{m}b,m+1)$.

  * •

For $b\in B_{m}$, $(b,m)\sim(\sigma^{-1}_{m}b,m+1)$.

The relation $\sim$ on the set $\mathcal{B}$ is called the Markov equivalence.
The first move corresponds to inserting a braid and its inverse below and
above an existing braid respectively. The second corresponds to adding a
strand to the right of existing braid in such a way that it crosses the strand
previously at the extreme right, below the braid. When viewed from the other
side of the plane of the braid it corresponds to shifting the braid to the
right by a position, inserting a strand in the first position in such a way
that it crosses the strand in second position below the braid.

Thus the second and third Markov moves, could be rewritten to give us the
following theorem.

######  Theorem 4.5.

The equivalence relation $\cong$ generated by the relations

  1. (1)

For $a,b\in B_{m}$, $m>1$, $(b,m)\cong(aba^{-1},m)$.

  2. (2)

For $i_{k}\leq m-1$,
$(\prod_{k=1}^{m}\sigma_{i_{k}}^{\epsilon_{k}},m)\cong(\sigma_{1}\prod_{k=1}^{m}\sigma_{{i_{k}}+1}^{\epsilon_{k}},m+1)$.

  3. (3)

For $i_{k}\leq m-1$,
$(\prod_{k=1}^{m}\sigma_{i_{k}}^{\epsilon_{k}},m)\cong(\sigma^{-1}_{1}\prod_{k=1}^{m}\sigma_{{i_{k}}+1}^{\epsilon_{k}},m+1)$.

is the Markov equivalence

######  Theorem 4.6 (Markov).

For $i=1,2$, let $m_{i}>1$ be integers and $b_{i}\in B_{m_{i}}$. Then the
links $\lambda(b_{1},m_{1})$ and $\lambda(b_{2},m_{2})$ are isotopic if and
only if $(b_{1},m_{1})\sim(b_{2},m_{2})$.

To state and equivalent condition for stable equivalence of links, consider
the equivalence relation $\approx$ on $\mathcal{B}$ generated by

  * •

For any $\beta_{1},\beta_{2}\in\mathcal{B}$ such that $\beta_{1}\sim\beta_{2}$
, $\beta_{1}\approx\beta_{2}$.

  * •

For $m_{1},m_{2}\in\mathbb{N}$ such that $b\in B_{m_{1}},B_{m_{2}}$,
$(b,m_{1})\approx(b,m_{2})$

######  Lemma 4.7.

Two links are stably equivalent if and only if given
$\lambda(b_{1},m_{1})=l_{1}$ and $\lambda(b_{2},m_{2})=l_{2}$, then
$(b_{1},m_{1})\approx(b_{2},m_{2})$.

###### Proof.

The fact that $(b_{1},m_{1})\approx(b_{2},m_{2})$ implies
$\lambda(b_{1},m_{1})\equiv\lambda(b_{2},m_{2})$ follows from the Markov’s
Theorem and Remark 4.3. For the converse, let $l_{1}$ and $l_{2}$ be two links
stably equivalent to each other, such that $\lambda(b_{1},m_{1})=l_{1}$ and
$\lambda(b_{2},m_{2})=l_{2}$. It is easy to see that, for some
$k_{1},k_{2}\geq 0$, $\lambda(b_{1},m_{1}+k_{1})$ is isotopic to
$\lambda(b_{2},m_{2}+k_{2})$ (we can in fact take one of $k_{1}$ and $k_{2}$
to be $0$). Then by Markov’s theorem, $(b_{1},m_{1}+k)\sim(b_{2},m_{2})$,
hence $(b_{1},m_{1})\approx(b_{2},m_{2})$. ∎

##  5\. Stable links and Infinite braids

In the previous section, we recalled the well known formulation of knot theory
in terms of braid groups. However, to formulate in terms of predicate
calculus, we shall reformulate this in terms of a single braid group
$B_{\infty}$. We shall do this by replacing the usual formulation of Markov’s
theorem by its mirror, which is Theorem 4.5 above.

######  Definition 5.1.

The braid group $B_{\infty}$ is the group generated by the set
$\\{\sigma_{i}\\}_{i\in\mathbb{N}}$ with the relations

  1. (1)

$\sigma_{i}\cdot\sigma_{j}=\sigma_{j}\cdot\sigma_{i}$, where
$i,j\in\mathbb{N},i\geq j+2$

  2. (2)

$\sigma_{i}\cdot\sigma_{i+1}\cdot\sigma_{i}=\sigma_{i}\cdot\sigma_{i+1}\cdot\sigma_{i}$,
where $i\in\mathbb{N}$.

Note that each braid group $B_{n}$ can be regarded as a subset of
$B_{\infty}$. Observe that there is an injective homomorphism $T:B_{\infty}\to
B_{\infty}$, which we call the _shift_ , determined by

$T(\sigma_{i})=\sigma_{i+1}.$

Let $\sigma=\sigma_{1}$ and $\bar{\sigma}=\sigma_{1}^{-1}$. Then observe that
$\sigma_{i}=T^{i-1}(\sigma)$. Thus, the translates of $\sigma$ by the semi-
group generated by $T$ generate $B_{\infty}$.

Consider the equivalence relation $\equiv$ on the group $B_{\infty}$ generated
by

  1. (1)

For $a,b\in B_{\infty}$, $aba^{-1}\equiv b$ .

  2. (2)

For $b\in B_{\infty}$, $b\equiv\sigma T(b)$ .

  3. (3)

For $b\in B_{\infty}$, $b\equiv\bar{\sigma}T(b)$.

We formulate stable equivalence of links in terms of $B_{\infty}$.

######  Theorem 5.2.

There is a surjective function $\Lambda:B_{\infty}\to\mathcal{L}$ so that, for
braids $b_{1},b_{2}\in B_{\infty}$, $\Lambda(b_{1})=\Lambda(b_{2})$ if and
only if $b_{1}\equiv b_{2}$.

###### Proof.

We begin by constructing the function $\Lambda$. For each $n>1$, there is a
homomorphism $f_{n}:B_{n}\to B_{\infty}$ determined by
$f_{n}(\sigma_{i})=\sigma_{i}$. The function is well defined because the braid
relations are preserved in $B_{\infty}$. These functions determine a function

$f:\mathcal{B}\to B_{\infty}$

given by

$f(b,m)=f_{m}(b)$

Observe that

$f^{-1}(b)=\\{(b,m)|b\in\ B_{m}\\}$

By lemma 4.7 , the links $\lambda(b,m_{1})$ and $\lambda(b,m_{2})$ are stably
equivalent for $m_{1}$ and $m_{2}$ such that $b\in B_{m_{1}}$ and $b\in
B_{m_{2}}$. Thus $\lambda$ and $f$ induce a function

$\Lambda:B_{\infty}\to\mathcal{L}$

given by

$\Lambda(b)=\lambda(f^{-1}(b))$

The fact that the map is surjective follows from Alexander’s Theorem. Now we
prove that $\Lambda(b_{1})=\Lambda(b_{2})\Leftrightarrow b_{1}\equiv b_{2}$.
Consider $b_{1},b_{2}\in B_{\infty}$ such that
$\Lambda(b_{1})=\Lambda(b_{2})$. Lemma 4.7 implies that for any $x\in
f^{-1}(b_{1})$ and $y\in f^{-1}(b_{2})$, $x\approx y$. In order to prove that
$\Lambda(b_{1})=\Lambda(b_{2})\implies b_{1}\equiv b_{2}$, it suffices to
prove that for $x,y\in\mathcal{B}$, $x\approx y\implies f(x)\equiv f(y)$. In
terms of the generating set of the relation ($\approx$), it translates to
proving the following

  1. (1)

For $b\in B_{m_{1}},B_{m_{2}}$, $f(b,m_{1})\equiv f(b,m_{2})$

  2. (2)

For $a,b\in B_{m}$, $f(b,m)\equiv f(aba^{-1},m)$.

  3. (3)

For $b\in B_{m}$, $f(b,m)\equiv f(\sigma_{1}b,m+1)$

  4. (4)

For $b\in B_{m}$, $f(b,m)\equiv f(\sigma_{1}^{-1}b,m+1)$.

The relation $f(b,m_{1})\equiv f(b,m_{2})$ follows from the fact that
$f(b_{1},m_{1})=f(b_{1},m_{2})$ and $\equiv$ is an equivalence relation.
$f(b,m)\equiv f(aba^{-1},m)$ follows from the first axiom of generating set of
$\equiv$. The third and fourth conditions are easy to verify.

In order to prove that $b_{1}\equiv
b_{2}\implies\Lambda(b_{1})=\Lambda(b_{2})$, from Theorem 4.5 it suffices to
check that for some $a_{1}\in f^{-1}(b_{1})$ and $a_{2}\in f^{-1}(b_{2})$,
$a_{1}\approx a_{2}$. Since Markov moves generate the equivalence relation
$\equiv$ on $B_{\infty}$ , it suffices to check that if two elements are
related to each other by a Markov move then the elements in their inverse
images are $\approx$ equivalent to each other.

Consider the first Markov move for $B_{\infty}$, $b\equiv aba^{-1}$. For an
appropriate $m$ such that $b,aba^{-1}\in B_{m}$, $(aba^{-1},m)\sim(b,m)$. Thus
from Theorem 4.5, $\lambda(aba^{-1})=\lambda(b)$. Similarly,
$(b,m)\sim(\sigma_{1}^{\pm 1}b,m+1)$. Thus $b_{1}\equiv
b_{2}\implies\Lambda(b_{1})=\Lambda(b_{2})$. ∎

##  6\. Knots as a canonical model

From the above we know that equivalence between links can be established by
checking if the corresponding elements in the braid group are related by a
sequence of moves on $B_{\infty}$ induced by the equivalence relation
$\equiv$. Now we prove that the braid group is the canonical model for the
link axioms and thus any model for these axioms can be used to distinguish
knots.

######  Theorem 6.1.

$(B_{\infty},T,\cdot,\equiv,\sigma_{1},\sigma_{1}^{-1})$ is a link model.

###### Proof.

We begin by proving that
$(B_{\infty},T,\cdot,\equiv,\sigma_{1},\sigma_{1}^{-1})$ satisfies the second
braid axiom. From the definitions of $B_{\infty}$ and $T$, it is easy to
derive that $(B_{\infty},T,\cdot,\equiv,\sigma_{1},\sigma_{1}^{-1})$ satisfies
the other link axioms. Consider an arbitrarily chosen element $b\in
B_{\infty}$. Since $B_{\infty}$ is generated by the set
$\\{\sigma_{i}\\}_{i\in\mathbb{N}}$, $b$ can be represented in terms of
generators as $\prod_{k=1}^{n}{\sigma_{i_{k}}^{\epsilon_{k}}}$, where
$i_{k}\in\mathbb{N}$ and $\epsilon_{k}$ is 1 or -1. This leads us to the
following equality

$\sigma_{1}\cdot
T^{2}(b)=\sigma_{1}\cdot\prod_{k=1}^{n}{\sigma_{i_{k}+2}^{\epsilon_{k}}}$

From the definition of $B_{\infty}$, we know that $\sigma_{i}$ and
$\sigma_{j}$ commute with respect to the product operation if $|i-j|\geq 2$.
This implies that for $i_{k}\in\mathbb{N}$,

$\sigma_{1}\cdot{\sigma_{{i_{k}}+2}^{\epsilon_{k}}}={\sigma_{i_{k}+2}^{\epsilon_{k}}}\cdot\sigma_{1}$

which further implies that

$\sigma_{1}\cdot\prod_{k=1}^{n}{\sigma_{{i_{k}}+2}^{\epsilon_{k}}}=\prod_{k=1}^{n}{\sigma_{i_{k}+2}^{\epsilon_{k}}}\cdot\sigma_{1}$

. Since $b$ was an arbitrarily chosen element of $B_{\infty}$, it follows that

$\sigma\cdot T^{2}(b)=T^{2}(b)\cdot\sigma\quad\forall b\in B_{\infty}$

. ∎

######  Definition 6.2 (Canonical Model).

For any signature $L$ and a set of sentences $\mathbb{T}$ in the language $L$,
a structure $A$ is said to be a _canonical model_ if

  * •

$A\models\mathbb{T}$

  * •

Every element of $A$ is of the form $t^{A}$, where $t$ is a closed term of
$L$.

  * •

If $B$ is an $L$-structure and $B\models\mathbb{T}$, there is a unique
homomorphism of structures $f:A\rightarrow B$.

Now we prove that $(B_{\infty},T,\cdot,\equiv,1,\sigma_{1},\sigma_{1}^{-1})$
is a canonical model for the link axioms. In order to do so, consider a model
of the link axioms
$(S,T_{1},*,\equiv^{\prime},1^{\prime},\sigma_{1}^{\prime},\bar{\sigma}_{1}^{\prime})$
and a map $f:B_{\infty}\rightarrow S$ such that

$\displaystyle f(1)$ $\displaystyle=1^{\prime}$ $\displaystyle f(\sigma_{1})$
$\displaystyle=\sigma_{1}^{\prime}$ $\displaystyle f(\sigma_{i})$
$\displaystyle=T_{1}^{i-1}(\sigma_{1}^{\prime})$ $\displaystyle f(b_{1}\cdot
b_{2})$ $\displaystyle=f(b_{1})*f(b_{2})$

The last condition suffices to extend the function to $B_{\infty}$ using the
image on the generating set. However it remains to be proved that it is well
defined.

######  Lemma 6.3.

The map $f:B_{\infty}\rightarrow S$ is well defined.

###### Proof.

In order to prove that the map is well defined, it suffices to prove that

  1. (1)

$T_{1}^{i}(\sigma_{1}^{\prime})*T_{1}^{j}(\sigma_{1}^{\prime})=T_{1}^{j}(\sigma_{1}^{\prime})*T_{1}^{i}(\sigma_{1}^{\prime})$,
For $i,j$ such that $j\geq i+2$

  2. (2)

$T_{1}^{i}(\sigma_{1}^{\prime})*T_{1}^{i+1}(\sigma_{1}^{\prime})*T_{1}^{i}(\sigma_{1}^{\prime})$
=
$T_{1}^{i+1}(\sigma_{1}^{\prime})*T_{1}^{i}(\sigma_{1}^{\prime})*T_{1}^{i+1}(\sigma_{1}^{\prime})$

Since
$(S,T_{1},*,\equiv^{\prime},1^{\prime}\sigma_{1}^{\prime},\bar{\sigma}_{1}^{\prime})$
is a model of the link axioms,

$\sigma_{1}^{\prime}\cdot
T^{2}(b)=T^{2}(b)\cdot\sigma_{1}^{\prime},\quad\forall b\in S$

Consider two arbitrarily chosen natural numbers $i$ and $j$ such that
$j-i-2\geq 0$. If we substitute $T_{1}^{j-i-2}(\sigma_{1}^{\prime})$ for $b$
we get,

$\sigma_{1}^{\prime}\cdot
T_{1}^{2}(T_{1}^{j-i-2}(\sigma_{1}^{\prime}))=T_{1}^{2}(T_{1}^{j-i-2}(\sigma_{1}^{\prime}))\cdot\sigma_{1}^{\prime}$

Which further leads to the equality,

$T_{1}^{i}(\sigma_{1}^{\prime}\cdot(T_{1}^{j-i}(\sigma_{1}^{\prime}))=T_{1}^{i}((T_{1}^{j-i}(\sigma_{1}^{\prime}))\cdot\sigma_{1}^{\prime})$

From the homomorphism action we get,

$T_{1}^{i}(\sigma_{1}^{\prime})\cdot
T_{1}^{i}(T_{1}^{j-i}(\sigma_{1}^{\prime}))=T_{1}^{i}(T_{1}^{j-i}(\sigma_{1}^{\prime}))\cdot
T_{1}^{i}(\sigma_{1}^{\prime})$ $T_{1}^{i}(\sigma_{1}^{\prime})\cdot
T_{1}^{j}(\sigma_{1}^{\prime})=T_{1}^{j}(\sigma_{1}^{\prime})\cdot
T_{1}^{i}(\sigma_{1}^{\prime})$

Thus condition (1) holds. From the first braid axiom it follows that,

$\sigma_{1}^{\prime}\cdot
T_{1}(\sigma_{1}^{\prime})\cdot\sigma_{1}^{\prime}=T_{1}(\sigma_{1}^{\prime})\cdot\sigma_{1}^{\prime}\cdot
T_{1}(\sigma_{1}^{\prime})$

Given $i\in\mathbb{N}$, $T_{1}^{i}$ is a homomorphism. By applying $T_{1}^{i}$
to the both the sides of the above equation,

$T_{1}^{i}(\sigma_{1}^{\prime})*T_{1}^{i+1}(\sigma_{1}^{\prime})*T_{1}^{i}(\sigma_{1}^{\prime})=T_{1}^{i+1}(\sigma_{1}^{\prime})*T_{1}^{i}(\sigma_{1}^{\prime})*T_{1}^{i+1}(\sigma_{1}^{\prime})$

Thus $f$ is well defined. ∎

######  Theorem 6.4.

$(B_{\infty},T,\cdot,\equiv,1,\sigma_{1},\sigma_{1}^{-1})$ is a canonical
model for link axioms.

###### Proof.

From Theorem 6.1, we know that
$(B_{\infty},T,\cdot,\equiv,\sigma_{1},\sigma_{1}^{-1})$ is a model of the
link axioms and thus the first axiom in the definition of a canonical model
holds true. Since every element in $B_{\infty}$ is of the form
$\prod_{k=1}^{n}T^{i_{k}}(\sigma_{1}^{\epsilon_{k}})$, where
$i_{k}\in\mathbb{N}\cup\\{0\\}$ and $\epsilon_{k}$ is 1 or -1, it follows that
every element is a closed term of $L$. Let
$\prod_{k=1}^{n}{\sigma_{i_{k}}^{\epsilon_{k}}}$ be an arbitrarily chosen
element of $B_{\infty}$. From the definition of $T$ it follows that

$\displaystyle f\circ T(\prod_{k=1}^{n}{\sigma_{i_{k}}^{\epsilon_{k}}})$
$\displaystyle=f(\prod_{k=1}^{n}{\sigma_{i_{k}+1}^{\epsilon_{k}}})$

Since $f$ is a group homomorphism,

$\displaystyle f(\prod_{k=1}^{n}{\sigma_{i_{k}+1}^{\epsilon_{k}}})$
$\displaystyle=\prod_{k=1}^{n}f({\sigma_{i_{k}+1}^{\epsilon_{k}}})$
$\displaystyle=\prod_{k=1}^{n}T^{{i_{k}}+1}_{1}(\sigma_{1}^{\prime\epsilon_{k}})$
$\displaystyle=\prod_{k=1}^{n}T_{1}\circ
T_{1}^{i_{k}}({\sigma_{1}^{\prime\epsilon_{k}}})$ $\displaystyle=T_{1}\circ
f(\prod_{k=1}^{n}{\sigma_{i_{k}}^{\epsilon_{k}}})$

Which implies that

$\displaystyle f\circ T$ $\displaystyle=T_{1}\circ f$

In order to prove that $f$ is a homomorphism of models, it now suffices to
prove that if two elements are related by any of the generating relations of
the stable equivalence, then their images under $f$ are related to each other.
Since
$(S,T_{1},*,\equiv^{\prime},1,\sigma^{\prime}_{1},\bar{\sigma}_{1}^{\prime})$
satisfies the Markov move axioms and $f$ preserves multiplication and
identity,

$x,y,z,\in B_{\infty},((y\cdot z=1)\implies(f(y\cdot x\cdot
z)\equiv^{\prime}f(x)))$

From the equality it follows that $f\circ T=T_{1}\circ f$,

$\sigma^{\prime}_{1}*T_{1}(f(x))=f(\sigma_{1}\cdot T(f(x)))$

and

$\bar{\sigma}^{\prime}_{1}*T_{1}(f(x))=f(\sigma_{1}^{-1}\cdot T(f(x)))$

hence it follows that

$f(x)\equiv^{\prime}f(\sigma_{1}\cdot T(f(x)))$

$f(x)\equiv^{\prime}f(\sigma_{1}^{-1}\cdot T(f(x)))$

The uniqueness of $f$ remains to be proved. Any homomorphism $g$ between the
given models maps $\sigma_{1}$ to $\sigma_{1}^{\prime}$ and has to satisfy the
condition $g\circ T$ = $T_{1}\circ g$. By applying induction, it follows that
$g\circ T^{i}(\sigma_{1})=T^{i}(g(\sigma_{1}))=T^{i}(f(\sigma_{1}))$ for every
$i\in\mathbb{N}$. Thus for any given homomorphism $g$ and any given
$i\in\mathbb{N}$, image of $g(\sigma_{i})$ is $T_{1}^{i}(f(\sigma_{1}))$.
Since the elements of the set $\\{\sigma_{i}\\}_{i\in\mathbb{N}}$ generate
$B_{\infty}$, it follows that $g=f$. ∎

## Appendix: Topological background

###  6.1. Knots and Braids

In order to understand how the above axioms constitute a model of the knots,
we introduce the following conceptual apparatus through which knots can be
reduced to braid groups.

######  Definition 6.5 (Braid Diagrams).

A braid diagram is a set $D\subset\mathbb{R}\times I$ split into topological
intervals called the strands of D such that

  1. (1)

The projection $\mathbb{R}\times I\rightarrow I$ maps each strand
homeomorphically onto I.

  2. (2)

Every point of $\mathbb{N}\times\\{0,1\\}$ is an end point of a unique strand.

  3. (3)

Every point of $\mathbb{R}\times I$ belongs to at most two strands. At each
intersection point of two strands, these strands meet transversally. At every
intersection, one of the intersecting strands is labelled ’undergoing’ and the
other strand is labelled ’overgoing’.

######  Remark 6.6.

Transversality in condition 3 means that in a neighbourhood of a crossing, up
to homeomorphism, D is like the set $\\{(x,y)|xy=0\\}$ . Compactness of
strands and condition(iii) ensures that the number of double points are
finite.

Two braid diagrams $D$ and $D^{\prime}$ are said to be isotopic if there is a
continuous map $F:D\times I\rightarrow\mathbb{R}\times I$ such that for each
$s\in I$, $D_{s}=F(D\times\\{s\\})\subset\mathbb{R}\times I$ is a braid
diagram preserving $D_{0}=D$ and $D_{1}=D^{\prime}$. It is understood that F
maps the crossings of D to crossings of $D_{s}$ while preserving the
information about when a strand goes under or over the other strand.An example
of braid diagram isotopy is given in the figure below.

The term braid diagram shall be here on used to denote the isotopy class of a
braid diagram. A product $*$ on the isotopy classes of braid diagrams is
defined by associating the diagram $D_{1}*D_{2}$ to the diagram obtained by
placing $D_{1}$ on top of $D_{2}$ and ’squeezing’ the resultant diagram into
$\mathbb{R}\times I$, i.e., (x, t)$\rightarrow$(x, t/2). It is easy to see
that the product is well defined and the braid diagram
$e=\cup_{k=1}^{n}\\{(k,t)|t\in[0,1]\\}$, is the identity. The product is
associative because any element of the form $(a*b)*c$ can be isotoped to
$a*(b*c)$ through a continuous map defined as follows.

$F(x,t,\theta)=\begin{cases}(1-\theta)(x,t)+\theta(x,2t),&\quad
t\in[0,1/4],\\\ (1-\theta)(x,t)+\theta(x,t+1/4),&\quad t\in[1/4,1/2],\\\
(1-\theta)(x,t)+\theta(x,(t+1)/2),&\quad t\in[1/2,1].\\\ \end{cases}$

To define a map from Braid Group $B_{n}$ to the set of n-braid diagrams
$\mathtt{B_{n}}$ upto isotopy, we define an equivalence relation on
$\mathtt{B_{n}}$ generated by a set of moves called the reidemeister moves.

######  Definition 6.7 (Reidemeister Moves).

The transformations of the braid diagrams $\Omega_{2},\Omega_{3}$ as shown in
the figure below and their inverses $\Omega_{2}^{-1},\Omega_{3}^{-1}$ are
called Reidemeister moves.

Two distinct braid diagrams are said to be R-equivalent if they are related to
each other by a sequence of Reidemeister moves.

Observe that if there exist braid diagrams a, b, c and d such that a is R-
equivalent to c and b is R-equivalent to d, $a*b$ is R-equivalent to $c*d$. It
follows that the product $*$ on $\mathtt{B_{n}}$, the isotopy classes of braid
diagrams upto R-equivalence, is well defined and $\mathtt{B}_{n}$ is a monoid.
Consider the braid diagrams $\overline{\sigma}_{i}^{+}$ and
$\overline{\sigma}_{i}^{-}$ as in the figure below.

The following result implies that the elementary braid diagrams
$\overline{\sigma}_{i}^{+}$ and $\overline{\sigma}_{i}^{-}$ generate
$\mathtt{B}_{n}$ and $(\mathtt{B}_{n},*)$ is a group.

######  Lemma 6.8.

R-equivalent classes of elementary braid diagrams $\overline{\sigma}_{i}^{+}$
and $\overline{\sigma}_{i}^{-}$ generate $\mathtt{B}_{n}$ as a monoid. Further
each element $\beta\in\mathtt{B}_{n}$ has a two sided inverse $\beta^{-1}$ in
$\mathtt{B}_{n}$.

The maps $\phi_{1_{n_{\epsilon}}}:B_{n}\to\mathtt{B}_{n}$ such that
$\phi_{1_{n_{\epsilon}}}(\sigma_{i})=\overline{\sigma}^{\epsilon}_{i}$, are
well defined because the first axiom of braid groups corresponds to isotopy of
braid diagrams and the second axiom corresponds to the second Reidemeister
move. The following result says that it is an isomorphism of groups.

######  Theorem 6.9.

$\phi_{1_{n_{\epsilon}}}$ is an isomorphism of groups.

To construct Links from braid diagrams, we define the following set of objects
in $\mathbb{R}^{2}\times I$ called Geometric Braids.

######  Definition 6.10 (Geometric Braids).

A geometric braid on $n\geq 2$ strings is a set $b\subset\mathbb{R}^{2}\times
I$ formed by the $n$ disjoint topological intervals called the strings of $b$,
such that

  1. (1)

$\pi_{3}:\mathbb{R}^{2}\times I\rightarrow I$ ,i.e., the projection onto I,
maps each string homeomorphically onto I.

  2. (2)

$b\cap(\mathbb{R}^{2}\times\\{0\\})=\\{(k,0,0)\\}_{k=1}^{n}$

  3. (3)

$b\cap(\mathbb{R}^{2}\times\\{1\\})=\\{(k,0,1)\\}_{k=1}^{n}$

Two geometric braids $b$ and $b^{\prime}$ are said to be isotopic if there is
a continuous map, $F:b\times I\rightarrow R^{2}\times I$ such that

  1. (1)

$F_{s}:b\rightarrow\mathbb{R}^{2}\times I$ sending $x\in b$ to F(x, s) is an
embedding, whose image is a geometric braid on n strings.

  2. (2)

$F_{0}=id_{0}:b\rightarrow b$

  3. (3)

$F_{1}(b)=b^{\prime}$

######  Theorem 6.11.

F extends to an isotopy of $\mathbb{R}^{2}\times I$ which is identity on
boundaries.

The map $i:\mathbb{R}\times I-\mathbb{R}^{2}\times I$ given by
$i(x,t)=(x,0,t)$ embeds braid diagrams in $R^{2}\times I$. Pushing the
undergoing strand in a small neighbourhood of every crossing into
$\mathbb{R}\times(0,\infty)\times I$ by appropriately increasing the second
co-ordinate of the strand while keeping the first and third constant, one
obtains a geometric n-braid. Observe that the geometric braids constructed
from isotopic braid diagrams are isotopic.

The above construction induces a map $\phi_{2_{n}}$ from the isotopy classes
of n-braid diagrams to $\mathbb{B}_{n}$, the set of geometric n-braids upto
isotopy. Projecting a geometric braid onto its first and third co-ordinates
and marking the intersecting strand with greater value of the second co-
ordinate in a neighbourhood of intersection as undercrossing and the other as
overcrossing in the neighbourhood, we obtain a braid diagram. The image of
this braid diagram under $\phi_{2_{n}}$ is isotopic to the original geometric
braid. Thus the map $\phi_{2_{n}}$ is surjective.

The following theorem makes explicit the relationship between braid diagrams
and geometric braids.

######  Theorem 6.12.

$\phi_{2_{n}}(b_{1})=\phi_{2_{n}}(b_{2})$ if and only if $b_{1}$ is
R-equivalent to $b_{2}$.

######  Corollary 6.13.

$\phi_{2_{n}}\circ\phi_{1_{n_{\epsilon}}}:B_{n}\rightarrow\mathbb{B}_{n}$ is
bijective.

If $f:(0,\infty)\to(0,1)$ is an order preserving homeomorphism, then the map
$\phi_{3_{n}}:R^{2}\times I\to D\times S^{1}$ where

$\phi_{3_{n}}(r(cos(\theta),sin(\theta)),t)=(f(r)(cos(\theta),sin(\theta)),e^{it})$

induces a well defined map from geometric $n$-braids to isotopic classes of
Links.

The map $\phi:\mathcal{B}\to L$ obtained by composition of the above maps,
$\phi(b,n)=\phi_{3_{n}}\circ\phi_{2_{n}}\circ\phi_{1_{n_{+}}}(b)$, assigns an
isotopy class of links to each braid which could be labelled as ’closing the
braid’. Markov’s Theorem and Alexander’s Theorem can thus be reformulated in
terms of $\phi$.

######  Theorem 6.14 (Alexander).

$\phi$ is surjective.

######  Theorem 6.15 (Markov).

$\phi(b_{1},m_{1})=\phi(b_{2},m_{2})$ if and only if
$(b_{1},m_{1})\sim(b_{2},m_{2})$.

## References

  * [1] W. Hodges.  Model theory, volume 42.  Cambridge Univ Pr, 1993.
  * [2] C. Kassel and V.G. Turaev.  Braid groups.  Springer Verlag, 2008.
  * [3] L.H. Kauffman.  On knots, volume 115.  Princeton Univ Pr, 1987.