Paper styleguide

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