Document Status: Complete notation reference Source: Mitankin, P. N. (2005). Universal Levenshtein Automata — Building and Properties. Master's Thesis, Sofia University "St. Kliment Ohridski" (supervisor: S. Mihov). Related journal generalisation: Mitankin, Mihov & Schulz (2011), TCS 412(22):2340–2355, doi:10.1016/j.tcs.2011.01.013. Last Updated: 2025-11-11
This glossary provides a comprehensive reference for all mathematical notation, symbols, functions, and terminology used in the Universal Levenshtein Automata thesis and documentation.
Related Documents:
| Symbol | Meaning | Page |
|---|---|---|
$\chi$ | Metasymbol: $\varepsilon$ (standard), t (transposition), ms (merge/split) | 3 |
$d^\chi _L(v, w)$ | Levenshtein distance between v and w | 3-5 |
| i#e | Fixed-word position: position i, error count e | 9 |
| I + i#e | Universal non-final position | 30 |
| M + i#e | Universal final position | 33 |
$A^\forall ,\chi _n$ | Universal Levenshtein automaton | 30 |
| h_n(w, x) | Bit vector encoding of word pair | 51 |
$\beta (x, w)$ | Characteristic vector | 17 |
$\le ^\chi _s$ | Subsumption relation | 18 |
$\sqcup A$ | Subsumption closure | 21 |
\chi$ (Chi) - Distance Variant MetasymbolDefinition: $\chi \in$ $\{\varepsilon , t, \text{ms}\}$
\chi = \varepsilon$ (or $\chi = ^{2})$: Standard Levenshtein distance\chi = t$: Levenshtein distance with transposition\chi =$ ms: Levenshtein distance with merge and splitUsage: Throughout the thesis as a placeholder for any of the three variants
Example: $d^\chi _L$ means d²_L, $d^t_L$, or $d^\text{ms}_L$ depending on context
\Sigma * \times \Sigma * \to \mathbb{N}$Standard Levenshtein Distance (Page 3)
Minimum cost to transform v into w using:
Properties:
d^t_L$ : $\Sigma * \times \Sigma * \to \mathbb{N}$Levenshtein Distance with Transposition (Page 4)
Standard operations plus:
⚠️ WARNING: Does NOT satisfy triangle inequality!
d^t_L(\text{abcd}, \text{abdc})$ + $d^t_L(\text{abdc}, \text{bdac})$ < $d^t_L(\text{abcd}, \text{bdac})$d^\text{ms}_L$ : $\Sigma * \times \Sigma * \to \mathbb{N}$Levenshtein Distance with Merge/Split (Page 5)
Standard operations plus:
d^\chi _L$ : $\Sigma * \times \Sigma * \to \mathbb{N}$Generic notation for any of the above three distances
L^\chi _\text{Lev}(n, w)$ : $\mathcal{P}(\Sigma *)$Levenshtein Language (Page 6)
L^χ_Lev(n, w) = {v | d^χ_L(v, w) ≤ n}
The set of all words within distance n from w.
R^\chi (n, w)$ : $\mathcal{P}(\Sigma *)$Extension Function (Page 7)
Recursive decomposition of $L^\chi _\text{Lev}(n, w)$:
\chi = \varepsilon$: Includes insertion, deletion, substitution, match terms\chi = t$: Adds transposition term\chi =$ ms: Adds merge and split termsKey Property: $L^\chi _\text{Lev}(n, w)$ = $R^\chi (n, w)$
Standard Position (Page 9)
Compact notation for $\langle \langle i, 0\rangle, e\rangle$
w (0 \le i \le |w|)$(0 \le e \le n)$Language: L(i#e) = $L^\chi _\text{Lev}(n - e, w_{i+1}...w_p)$
Transposition Position (Page 10)
Compact notation for $\langle \langle i, 1\rangle, e\rangle$
Used when detecting transposition of w_{i+1} and w_{i+2}
Merge/Split Position (Page 10)
Compact notation for $\langle \langle i, 2\rangle, e\rangle$
Used when processing merge or split operations
Universal Non-Final Standard Position (Page 29)
Compact notation for $\langle \langle \lambda I.I+i, 0\rangle, e\rangle$
(-n \le i \le n)$(0 \le e \le n)$Constraint: $|i| \le e$
Universal Non-Final Transposition Position (Page 31)
Compact notation for $\langle \langle \lambda I.I+i, 1\rangle, e\rangle$
Universal Non-Final Split Position (Page 32)
Compact notation for $\langle \langle \lambda I.I+i, 2\rangle, e\rangle$
Universal Final Standard Position (Page 33)
Compact notation for $\langle \langle \lambda M.M+i, 3\rangle, e\rangle$
(-2n \le i \le 0)$(0 \le e \le n)$Constraint: $e \ge -i - n$
Universal Final Transposition Position (Page 34)
Compact notation for $\langle \langle \lambda M.M+i, 4\rangle, e\rangle$
Universal Final Split Position (Page 35)
Compact notation for $\langle \langle \lambda M.M+i, 5\rangle, e\rangle$
A^\text{ND},\chi _n(w)$Nondeterministic Levenshtein Automaton (Page 9)
A^ND,χ_n(w) = ⟨Σ, Q^ND,χ_n, I^ND,χ, F^ND,χ_n*, δ^ND,χ_n⟩
\Sigma \cup$ $\{\varepsilon\}$L^\chi _\text{Lev}(n, w)$A^D,\chi _n(w)$Deterministic Levenshtein Automaton (Page 23)
A^D,χ_n(w) = ⟨Σ, Q^D,χ_n, I^D,χ, F^D,χ_n, δ^D,χ_n⟩
\Sigma$L^\chi _\text{Lev}(n, w)$A^\forall ,\chi _n$Universal Levenshtein Automaton (Page 30)
A^∀,χ_n = ⟨Σ^∀_n, Q^∀,χ_n, I^∀,χ, F^∀,χ_n, δ^∀,χ_n⟩
\Sigma^\forall_n = \{x \in \{0,1\}^+ \mid \lvert x\rvert \le 2n + 2\}$\{h_n(w, x) | 0 \le n\}$Q^\text{ND},\chi _n$NFA State Set (Page 9)
For $\chi = \varepsilon$: $\{i#e | 0 \le i \le p \land 0 \le e \le n\}$
Plus transposition/split states for t, ms variants.
Q^D,\chi _n$DFA State Set (Page 23)
Sets of positions that are:
\le ^\chi _s$ (no position subsumes another)I^\chi _s$Universal Non-Final Position Set (Page 30-32)
All valid I-type positions for variant $\chi .$
For $\chi = \varepsilon$: $\{I + t#k | |t| \le k \land -n \le t \le n \land 0 \le k \le n\}$
M^\chi _s$Universal Final Position Set (Page 33-35)
All valid M-type positions for variant $\chi .$
For $\chi = \varepsilon$: $\{M + t#k | k \ge -t - n \land -2n \le t \le 0 \land 0 \le k \le n\}$
I^\chi _\text{states}$Universal Non-Final States (Page 38)
I^χ_states = {Q | Q ⊆ I^χ_s ∧ ∀q₁,q₂ ∈ Q (q₁ ⊀^χ_s q₂)} \ {∅}
Anti-chains of non-final positions.
M^\chi _\text{states}$Universal Final States (Page 38)
M^χ_states = {Q | Q ⊆ M^χ_s ∧ anti-chain ∧ valid constraints} \ {∅}
Anti-chains of final positions with additional constraints.
\delta ^\text{ND}$,$\chi _n$ : $Q^\text{ND},\chi _n \times (\Sigma \cup$ $\{\varepsilon\}$) $\to \mathcal{P}$($Q^\text{ND},\chi _n)$NFA Transition (Page 9-10)
Standard NFA transitions with $\varepsilon$-transitions for insertions.
\delta ^\text{ND}$,$\chi _n$* : $Q^\text{ND},\chi _n \times \Sigma$* $\to \mathcal{P}(Q^\text{ND},\chi _n)$Extended NFA Transition (Page 11)
Handles sequences with $\varepsilon$-closure.
\delta ^D,\chi _e$ : $Q^\text{ND},\chi \times$ {0,1}* $\to \mathcal{P}(Q^\text{ND},\chi )$Elementary Transition Function (Page 14-16)
Given position and bit vector, compute reachable positions.
\delta ^D,\chi _n$ : $Q^D,\chi _n \times \Sigma \to Q^D,\chi _n$DFA Transition (Page 23)
δ^D,χ_n(M, x) = ⊔_{π∈M} δ^D,χ_e(π, x)
Apply elementary transitions and subsumption closure.
\delta ^\forall ,\chi _e$ : $(I^\chi _s \cup M^\chi _s) \times \Sigma ^\forall _n \to \mathcal{P}(I^\chi _s \cup M^\chi _s)$Universal Elementary Transition (Page 46)
Extract relevant subvector, apply $\delta ^D,\chi _e,$ convert back to universal positions.
\delta ^\forall ,\chi _n$ : $Q^\forall ,\chi _n \times \Sigma ^\forall _n \to Q^\forall ,\chi _n$Universal Transition (Page 48)
δ^∀,χ_n(Q, x) = {
Δ if f_n(rm(Δ), |x|) = false
m_n(Δ, |x|) if f_n(rm(Δ), |x|) = true
}
where Δ = ⊔_{q∈Q} δ^∀,χ_e(q, x)
Includes diagonal crossing check and I/M conversion.
w[\pi ]$ : Relevant SubwordDefinition (Page 17): For position $\pi = i$#e, returns w_{i+1}...w_{i+k} where k = min(n - e + 1, p - i)
\beta (x, w)$ : Characteristic VectorDefinition (Page 17): $\beta$ : $\Sigma \times \Sigma * \to$ {0,1}*
β(x, w₁w₂...w_p) = b₁b₂...b_p where b_i = (1 if x = w_i else 0)
Example: $\beta ('a',$ "banana") = "101010"
Definition (Page 51): Returns window around position i
s_n(w, i) = w_{i-n}...w_{min(|w|, i+n+1)}
With padding: w_{-n+1} = ... = w_0 = $
Definition (Page 51): Encodes word pair (w, x) as bit vector sequence
h_n(w, x₁...x_t) = β(x₁, s_n(w,1))...β(x_t, s_n(w,t))
Key Property: $x \in$ $L^\chi _\text{Lev}(n, w)$ $\Leftrightarrow h_n(w, x) \in L(A^\forall,\chi _n)$
Definition (Page 39): Extracts relevant portion of bit vector for a universal position
For I + i#e: Extract from position (n + i + 1) For M + i#e: Extract from position (k + i + 1) where k = |input|
Definition (Page 42): Converts between non-final and final positions
m_n(I + i#e, k) = M + (i + n + 1 - k)#e
m_n(M + i#e, k) = I + (i - n - 1 + k)#e
Definition (Page 43): Checks if position crossed diagonal
For I + i#e: f_n(S, k) = true if $k \le 2n + 1 \land e \le i + 2n + 1 - k$
For M + i#e: f_n(S, k) = true if e > i + n
Definition (Page 45): Returns position with maximum (e - i) in a state
rm(A) = position with max(e - i)
Definition (Page 47): Returns valid input lengths for a state
For {I#0}: $\{k | n \le k \le 2n + 2\}$
For other states: Computed based on right-most element
\le ^\chi _s$ : Subsumption RelationDefinition (Page 18-19): Partial order on positions
For $\chi = \varepsilon$:
i#e ≤^ε_s j#f ⇔ f > e ∧ |j - i| ≤ f - e
Intuition: Position j#f subsumes i#e if j#f has enough extra errors to "cover" the position difference.
For universal positions (Page 36-37):
I + i#e ≤^χ_s I + j#f ⇔ i#e ≤^χ_s j#f
M + i#e ≤^χ_s M + j#f ⇔ i#e ≤^χ_s j#f
Properties:
\pi \le ^\chi _s \pi$\pi _{1} \le ^\chi _s \pi _{2} \land \pi _{2} \le ^\chi _s \pi _{1} \Rightarrow \pi _{1} = \pi _{2}$\pi _{1} \le ^\chi _s \pi _{2} \land \pi _{2} \le ^\chi _s \pi _{3} \Rightarrow \pi _{1} \le ^\chi _s \pi _{3}$<^\chi _s$ : Strict SubsumptionDefinition: $\pi _{1} <^\chi _s \pi _{2} \Leftrightarrow \pi _{1} \le ^\chi _s \pi _{2} \land \pi _{1} \ne \pi _{2}$
\sqcup A$ : Subsumption ClosureDefinition (Page 21, 47): Removes subsumed elements
⊔A = {π | π ∈ ⋃A ∧ ¬∃π' ∈ ⋃A (π' <^χ_s π)}
Returns maximal elements (anti-chain).
I^\chi$ : $\mathcal{P}(Q^\text{ND},\chi ) \to \mathcal{P}(P^\chi$)Concrete to Universal (Non-Final) (Page 44)
I^ε(A) = {I + (i - 1)#e | i#e ∈ A}
Shifts positions by -1 and adds I parameter.
M^\chi$ : $\mathcal{P}(Q^\text{ND},\chi ) \to \mathcal{P}(P^\chi$)Concrete to Universal (Final) (Page 44)
M^ε(A) = {M + i#e | i#e ∈ A}
Adds M parameter without shift.
I^\chi _s$ $\cup$ $M^\chi _s) \times \mathbb{N} \to$ $Q^\text{ND},\chi$Universal to Concrete (Page 52)
d(I + i#e, z) = (z + i)#e
d(M + i#e, z) = (z + i)#e
Substitutes parameter (I or M) with concrete value z.
Definition (Page 4): x₁...xₖ ↪ t removes first t characters
x₁...xₖ ↪ t = {
ε if t ≥ k
x_{t+1}...xₖ otherwise
}
Definition (Page 4): c < d means c is a prefix of d
\mu z[A]$ : MinimumDefinition (Page 14): The least z such that property A holds
Definition: !x means x is defined (not $\lnot$!)
\lnot$! : UndefinednessDefinition: $\lnot$!x means x is undefined
Definition: x def= y means x is defined to equal y
\Sigma$Alphabet: Finite set of symbols
\Sigma *$All words: Set of all finite sequences over $\Sigma$ (including empty word $\varepsilon )$
\Sigma ^{+}$Non-empty words: $\Sigma *$ \ $\{\varepsilon\}$
\varepsilon$Empty word: Word of length 0
Word length: Number of characters in w
\mathcal{P}(A)$Power set: Set of all subsets of A
\mathbb{N}$Natural numbers: {0, 1, 2, ...}
\mathbb{N} ^{+}$Positive integers: {1, 2, 3, ...}
\mathbb{Z}$Integers: {..., -2, -1, 0, 1, 2, ...}
States: Set of states
Initial state: Starting state (usually {0#0} or {I#0})
Final states: Accepting states
\delta$Transition function: Maps (state, symbol) to states
Language of automaton: Set of words accepted by A
L(\pi )$Language of state: Set of words accepted starting from state $\pi$
\mathcal{O}(f(n)$)Big-O: Upper bound on growth rate
Examples in thesis:
\mathcal{O}(n^{2})$\mathcal{O}(n^{2} \cdot 2^{2n})$d^t_L$ triangle inequality violation warningd^t_L$, $d^\text{ms}_L$L^\chi _\text{Lev}$, $R^\chi$A^{\text{ND},\chi}_n(w)$, $\delta^{\text{ND},\chi}_n$, $\text{Cl}_\varepsilon$\delta ^D,\chi _e, \beta , w[\pi ]$\le ^\chi _s, \sqcup , A^D,\chi _n(w)$A^\forall ,\chi _n, r_n, m_n, f_n,$ rm, ▽_ah_n, s_n, I^\chi , M^\chi , d$\chi = \varepsilon$ (standard) before tackling transposition/merge-splitd^t_L$ violates triangle inequality (affects subsumption logic)(\le ^\chi _s, \sqcup )$ correctly - critical for correctness(\beta , h_n)$ must be efficientFixed: i#e (concrete position i in specific word w) Universal: I + i#e (parametric, i is offset from I)
I-type: Non-final states (before reaching end of word) M-type: Final states (at or past end of word)
Conversion happens when crossing diagonal (detected by f_n).
i#$e \le ^\chi _s j$#f means j#f subsumes i#e (j#f recognizes more words)
In state sets, we keep only maximal elements (not subsumed by others).
h_n(w, x) produces a sequence of bit vectors (one per character of x) Each bit vector encodes matches with a window around that position in w
Only $d^t_L$ violates it! d²_L and $d^\text{ms}_L$ may satisfy it (not proven in thesis).
| To find... | Look for... |
|---|---|
| Distance definition | Section $2, d^\chi _L$ |
| Fixed-word position | Section 3, i#e |
| Universal position | Section 5, I + i#e, M + i#e |
| Subsumption | Section $4, \le ^\chi _s$ |
| Bit encoding | Section $5, h_n, \beta$ |
| Conversion I↔M | Section 5, m_n |
| Diagonal check | Section 5, f_n |
| Transition function | $\delta ^\text{ND}$,$\chi _n, \delta ^D,\chi _n, \delta ^\forall ,\chi _n$ |
| Construction algorithm | Section 6, Build_Automaton |
| Correctness proof | Section 5, Proposition 19 |
| Minimality proof | Section 7 |
End of Glossary
Last Updated: 2025-11-11 Notation Count: 50+ symbols and functions Cross-referenced: All sections covered
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |