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