Table of Contents

This is a growing list of notation and style decisions Pesho and I made during the writing of our paper, written down so that we don’t have to spend time on it again next time.

## Notation

- Alphabet
- \(\Sigma\), \(|\Sigma| = 4\)

- Sequences
- \(A = \overline{a_0\dots a_{n-1}} \in \Sigma^*\), \(|A| = n\)
- \(B = \overline{b_0\dots b_{m-1}} \in \Sigma^*\), \(|B| = m\)
- Edit distance \(\mathrm{ed}(A, B)\)
- \(A_{<i} = \overline{a_0\dots a_{i-1}}\)
- \(A_{\geq i} = \overline{a_i\dots a_{n-1}}\)
- \(A_{i\dots i’} = \overline{a_i\dots a_{i’-1}}\)

- Edit graph
- State \(\langle i, j\rangle\)
- Graph \(G(V, E)\) where \(V = \{\langle i,j\rangle | 0\leq i\leq n, 0\leq j\leq m\}\)
- Root state \(v_s = \langle 0,0\rangle\)
- Target state \(v_t = \langle n,m\rangle\)
- Distance \(d(u, v)\)
- Path \(\pi\)
- Shortest path \(\pi^*\)
- Cost of path \(cost(\pi)\), \(cost(\pi^*) = d(v_s, v_t) = \mathrm{ed}(A, B)\).

## Naming and style

Vertex, not node

Target, not end

Goes better with \(v_s \to v_t\) notation.

Substitution, not mismatch

Letter, not character

Runtime complexity, not just complexity or just runtime

LCS, not lcs

`\cref`

, not`\ref`