Liking cljdoc? Tell your friends :D

← Documentation Index

Universal Levenshtein Automata - Algorithms

Source: "Universal Levenshtein Automata - Building and Properties" (Petar Mitankin, 2005), Master's Thesis, Sofia University "St. Kliment Ohridski" Section: 6 - Building of $A^\forall ,\varepsilon _n, A^\forall ,t_n$ and $A^\forall$,ms_n (Pages 48-59)

This document extracts the complete algorithmic content from Section 6, including all pseudocode, type definitions, API functions, complexity analysis, and results tables.

Table of Contents

  1. Overview
  2. High-Level Algorithm (6.1)
  3. Type Definitions (6.2)
  4. API Functions (6.2)
  5. Detailed Algorithms (6.2)
  6. Complexity Analysis (6.3)
  7. Implementation Notes

Overview

Section 6 presents the complete construction algorithm for Universal Levenshtein Automata. The algorithm:

  • Uses breadth-first search (BFS) to generate all states
  • Handles cycles using HAS_NEVER_BEEN_PUSHED to avoid revisiting states
  • Builds $A^\forall ,\chi _n$ for all three distance variants: $\chi \in$ $\{\varepsilon , t, \text{ms}\}$
  • Achieves $\mathcal{O}(n^{2})$ states with polynomial construction time

Key Insight: The universal automaton is parameter-free and works for any word length by using parametric positions (I, M) instead of concrete word indices.

6.1 High-Level Algorithm

Summarized Pseudocode

This is the conceptual overview before the detailed implementation:

procedure Build_Automaton( n, χ );
begin
  PUSH_IN_QUEUE( {I#0} );
  while( not EMPTY_QUEUE() ) do begin
    st := POP_FROM_QUEUE();
    for b in Σ^∀_n do begin
      if( LENGTH(b) ∈ ∇_a(st) ) then begin
        nextSt := δ^∀,χ_n(st, b);
        if( not EMPTY_STATE(nextSt) ) then begin
          if( HAS_NEVER_BEEN_PUSHED(nextSt) ) then begin
            PUSH_IN_QUEUE(nextSt)
          end
          ADD_TRANSITION( <st, b, nextSt> )
        end
      end
    end
  end
end;

Algorithm Flow:

  1. Initialize queue with start state {I#0}
  2. While queue not empty:
    • Pop current state st
    • For each bit vector b $\in \Sigma ^\forall _n$ (strings of length 1 to 2n+2):
      • Check if $\text{LENGTH}(b) \in \nabla _a(\text{st})$ (length covers all positions)
      • Compute next state: $\text{nextSt} := \delta ^\forall ,\chi _n(\text{st}, b)$
      • If nextSt non-empty and never seen before:
        • Add to queue
        • Add transition <st, b, nextSt>

Critical Function: HAS_NEVER_BEEN_PUSHED(nextSt) ensures each state is generated exactly once (handles cycles in $A^\forall ,\chi _n).$

6.2 Type Definitions

I) Types

1) STATE
   Type: Finite set whose elements are POSITIONs
   Represents: A state in A^∀,χ_n

2) POSITION
   Type: Tuple <parameter, type, X, Y>
   Where:
     - parameter ∈ {I, M}     (encoded: I=0, M=1)
     - type ∈ {usual, t, s}   (encoded: usual=0, t=1, s=2)
     - X, Y ∈ Z               (integers)

   Examples:
     - I + i#e    → <I, usual, i, e>
     - It + i#e   → <I, t, i, e>
     - Is + i#e   → <I, s, i, e>
     - M + i#e    → <M, usual, i, e>
     - Mt + i#e   → <M, t, i, e>
     - Ms + i#e   → <M, s, i, e>

3) SET_OF_POINTS
   Type: Finite set whose elements are POINTs
   Represents: Intermediate computation results in δ^D,χ_e

4) POINT
   Type: Tuple <type, X, Y>
   Where:
     - type ∈ {usual, t, s}
     - X, Y ∈ Z

   Note: POINTs are like POSITIONs but without the parameter field

Key Distinction:

  • POSITION: Universal position with parameter (I or M) - used in $A^\forall ,\chi _n$
  • POINT: Fixed-word position without parameter - used in intermediate computations

6.2 API Functions

Queue Operations

1) PROCEDURE PUSH_IN_QUEUE( st : STATE );
   // Pushes st onto the global QUEUE

2) FUNCTION EMPTY_QUEUE() : BOOLEAN;
   // Returns TRUE iff QUEUE is empty

3) FUNCTION POP_FROM_QUEUE() : STATE;
   // Pops and returns an element from QUEUE

4) FUNCTION HAS_NEVER_BEEN_PUSHED( st : STATE ) : BOOLEAN;
   // Returns TRUE iff st has never been pushed to QUEUE
   // Critical for cycle handling!

Position Constructors and Accessors

5) FUNCTION NEW_POSITION( parameter : {I, M};
                          type : {usual, t, s};
                          x, y : INTEGER ) : POSITION;
   // Creates new POSITION with given components

6) FUNCTION GET_POSITION_PARAM( pos : POSITION ) : {I, M};
   // Returns the parameter field of pos

7) FUNCTION GET_POSITION_TYPE( pos : POSITION ) : {usual, t, s};
   // Returns the type field of pos

8) FUNCTION GET_POSITION_X( pos : POSITION ) : INTEGER;
   // Returns the X coordinate of pos

9) FUNCTION GET_POSITION_Y( pos : POSITION ) : INTEGER;
   // Returns the Y coordinate of pos

State Operations

10) FUNCTION EMPTY_STATE( st : STATE ) : BOOLEAN;
    // Returns TRUE iff st is the empty set

11) FUNCTION GET_FIRST_POSITION( st : STATE ) : POSITION;
    // Returns any element from st (order doesn't matter)

Transition Operations

12) PROCEDURE ADD_TRANSITION( st : STATE; b : STRING; nextSt : STATE );
    // Adds transition <st, b, nextSt> to the output AUTOMATON

Point Operations

13) FUNCTION EMPTY_SET_OF_POINTS( set : SETOFPOINTS ) : BOOLEAN;
    // Returns TRUE iff set is empty

14) FUNCTION NEW_POINT( type : {usual, t, s}; x, y : INTEGER ) : POINT;
    // Creates new POINT with given components

15) FUNCTION GET_POINT_TYPE( pt : POINT ) : {usual, t, s};
    // Returns the type field of pt

16) FUNCTION GET_POINT_X( pt : POINT ) : INTEGER;
    // Returns the X coordinate of pt

17) FUNCTION GET_POINT_Y( pt : POINT ) : INTEGER;
    // Returns the Y coordinate of pt

String Operations

18) FUNCTION SUB_STRING( s : STRING;
                         startPos : INTEGER;
                         length : INTEGER ) : STRING;
    // Returns s[startPos]s[startPos+1]...s[startPos+length-1]
    // Note: 1-indexed!

Global Variable

19) VAR CHI : {epsilon, t, ms};
    // Global variable encoding the distance variant
    // epsilon = 0, t = 1, ms = 2

Detailed Algorithms

Build_Automaton

Main construction procedure - builds $A^\forall ,\chi _n$ using BFS.

procedure Build_Automaton( n : INTEGER );
VAR st, nextSt : STATE;
    b          : STRING;
begin
  1  PUSH_IN_QUEUE( { NEW_POSITION(I, usual, 0, 0) } );
  2  while( not EMPTY_QUEUE() ) do begin
  3    st := POP_FROM_QUEUE();
  4    for b in { sym | sym : STRING and
                   1 <= LENGTH(sym) <= 2n+2 and
                   for all i( i in [1, LENGTH(sym)] =>
                     ( sym[i] = 0 or sym[i] = 1 ) ) } do begin
  5      if( Length_Covers_All_The_Positions(n, LENGTH(b), st) ) then begin
  6        nextSt := Delta(n, st, b);
  7        if( not EMPTY_STATE(nextSt) ) then begin
  8          if( HAS_NEVER_BEEN_PUSHED(nextSt) ) then begin
  9            PUSH_IN_QUEUE(nextSt)
 10          end
 11          ADD_TRANSITION(st, b, nextSt)
 12        end
 13      end
 14    end
 15  end
end;

Line-by-line:

  • Line 1: Start with initial state {I#0} (single position: I + 0#0)
  • Line 2-15: BFS loop
  • Line 3: Pop next state to process
  • Line 4: Iterate over all bit vectors $b \in$ {0,1}^+ with $1 \le |b| \le 2n+2$
  • Line 5: Check if $|b| \in \nabla _a$(st) (length compatibility check)
  • Line 6: Compute successor state via $\delta ^\forall ,\chi _n$
  • Line 7-12: If non-empty successor:
    • Line 8-10: Add to queue if first time seeing it
    • Line 11: Add transition regardless (may have multiple edges to same state)

Input Alphabet: $\Sigma^\forall_n = \{b \in \{0,1\}^+ \mid 1 \le \lvert b\rvert \le 2n+2\}$

Length_Covers_All_The_Positions

Checks if bit vector length $k \in \nabla _a$(st) - i.e., whether k "covers" all positions in state st.

function Length_Covers_All_The_Positions( n : INTEGER;
                                           k : INTEGER;
                                          st : STATE ) : BOOLEAN;
(* Returns true ⇔ k ∈ ∇_a(st) *)
VAR pos, pi, q : POSITION;
begin
 16 pos = GET_FIRST_POSITION(st);
 17 if( GET_POSITION_PARAM(pos) = I ) then begin
 18   if( st = { NEW_POSITION(I, usual, 0, 0) } ) then begin
      // Special case: initial state
      return( k >= GET_POSITION_X(pos) + n )
    end
    else begin
      // General I-type state
      for pi in st do begin
        if( k < 2*n + GET_POSITION_X(pi) - GET_POSITION_Y(pi) + 1 ) then begin
          return( false )
        end
      end
    end

  else begin
    // M-type state
    if( k < n ) then begin
      q := NEW_POSITION(M, usual, 0, n - k)
    end
    else begin
      q := NEW_POSITION(M, usual, n - k, 0)
    end

    for pi in st do begin
      if( pi <> q and (not Less_Than_Subsume(q, pi)) ) then begin
        return( false )
      end
    end
  end

  return( true )
end;

Logic:

Case 1: I-type state (st $\subseteq I^\chi _s)$

  • Subcase 1.1: Initial state {I#0}
    • Require: $k \ge n$ (bit vector must be at least length n)
  • Subcase 1.2: General I-type state
    • For all positions pi $\in$ st:
      • Require: $k \ge 2n + X$(pi) - Y(pi) + 1
    • If any position fails, return false

Case 2: M-type state (st $\subseteq M^\chi _s)$

  • Construct reference position q:
    • If k < n: q = M + 0#(n-k)
    • Otherwise: q = M + (n-k)#0
  • For all positions pi $\in$ st:
    • Check: pi = q OR $q <^\chi _s$ pi
    • If not, return false

Returns: true if all checks pass, false otherwise

Delta

Computes $\delta ^\forall ,\chi _n$(st, b) - the transition function of $A^\forall ,\chi _n.$

function Delta( n : INTEGER; st : STATE; b : STRING ) : STATE;
(* Delta(n, st, b) corresponds to δ^∀,χ_n(st, b) *)
VAR bAdd           : BOOLEAN;
    nextSt, deltaE : STATE;
    q, pi, p       : POSITION;
begin
  nextSt := {};

  for q in st do begin
    deltaE = Delta_E(n, q, b);

    if( not EMPTY_STATE(deltaE) ) then begin
      for pi in deltaE do begin
        bAdd := true;

        for p in nextSt do begin
          if( Less_Than_Subsume(pi, p) ) then begin
            // pi is subsumed by p, remove p
            nextSt := nextSt \ {p}
          end
          else begin
            if( p = pi or Less_Than_Subsume(p, pi) ) then begin
              // p subsumes pi or they're equal, don't add pi
              bAdd := false;
              goto LABEL1
            end
          end
        end

        LABEL1:
        if( bAdd ) then begin
          nextSt := nextSt ∪ {pi}
        end
      end
    end
  end

  if( F(n, RM(nextSt), LENGTH(b)) ) then begin
    nextSt := M(n, nextSt, LENGTH(b))
  end

  return( nextSt )
end;

Algorithm:

  1. Initialize: nextSt := {}
  2. For each position $q \in$ st:
    • Compute deltaE :$= \delta ^\forall ,\chi _e(q, b)$
    • For each resulting position pi $\in$ deltaE:
      • Try to add pi to nextSt, maintaining subsumption closure
      • Remove any $p \in$ nextSt subsumed by pi
      • Don't add pi if it's subsumed by or equal to any $p \in$ nextSt
  3. Diagonal crossing check: If f_n(rm(nextSt), |b|) is true:
    • Apply m_n conversion: nextSt := m_n(nextSt, |b|)
  4. Return: nextSt (with subsumption closure $\sqcup$ applied)

Key Insight: This implements the subsumption closure operator $\sqcup$ to keep states minimal (anti-chains).

Less_Than_Subsume

Checks $q1 <^\chi _s q2$ - the strict subsumption relation.

function Less_Than_Subsume( q1 : POSITION; q2 : POSITION ) : BOOLEAN;
(* Returns true ⇔ q1 <^χ_s q2 *)
VAR m : INTEGER;
begin
  if( GET_POSITION_TYPE(q1) <> usual or
      GET_POSITION_Y(q2) <= GET_POSITION_Y(q1) ) then begin
    return( false )
  end

  if( GET_POSITION_TYPE(q2) = t ) then begin
    m = GET_POSITION_X(q2) + 1 - GET_POSITION_X(q1)
  end
  else begin
    m = GET_POSITION_X(q2) - GET_POSITION_X(q1)
  end

  if( m < 0 ) then begin
    m = -m
  end

  return( m <= GET_POSITION_Y(q2) - GET_POSITION_Y(q1) )
end;

Subsumption Rules (from Definition 11):

For $\varepsilon$ (standard Levenshtein):

i#e <^ε_s j#f  ⇔  f > e  ∧  |j - i| ≤ f - e

For t (with transposition):

i#e   <^t_s j#f     ⇔  f > e  ∧  |j - i| ≤ f - e
i#e_t <^t_s j#f     ⇔  f > e  ∧  |j + 1 - i| ≤ f - e
i#e   <^t_s j#f_t   ⇔  false (different types)
i#e_t <^t_s j#f_t   ⇔  false (different types)

For ms (with merge/split):

i#e   <^ms_s j#f    ⇔  f > e  ∧  |j - i| ≤ f - e
i#e_s <^ms_s j#f    ⇔  f > e  ∧  |j - i| ≤ f - e
i#e   <^ms_s j#f_s  ⇔  false (different types)
i#e_s <^ms_s j#f_s  ⇔  false (different types)

Algorithm:

  1. Prerequisite checks:
    • q1 must be "usual" type (not t or s)
    • Y(q2) > Y(q1) (error count must be strictly greater)
  2. Compute distance: $m = |X(q2) \pm \delta - X(q1)|$ where $\delta = 1$ if q2 is type t, else 0
  3. Check subsumption: $m \le Y(q2) - Y(q1)$

Delta_E

Computes $\delta ^\forall ,\chi _e(q, b)$ - elementary transition for a single universal position.

function Delta_E( n : INTEGER; q : POSITION; b : STRING ) : STATE;
(* Delta_E(n, q, b) corresponds to δ^∀,χ_e(q, b) *)
var deltaED : SETOFPOINTS;
    st      : STATE;
    pi      : POINT;
begin
  deltaED := Delta_E_D( n,
                        NEW_POINT( GET_POSITION_TYPE(q),
                                   GET_POSITION_X(q),
                                   GET_POSITION_Y(q) ),
                        R(n, q, b) );

  if( EMPTY_SET_OF_POINTS(deltaED) ) then begin
    return( {} )
  end

  st := {};

  if( GET_POSITION_PARAM(q) = I ) then begin
    // I-type position: shift X coordinate by -1
    for pi in deltaED do begin
      st := st ∪ { NEW_POSITION( I,
                                  GET_POINT_TYPE(pi),
                                  GET_POINT_X(pi) - 1,
                                  GET_POINT_Y(pi) ) }
    end
  end
  else begin
    // M-type position: keep coordinates as-is
    for pi in deltaED do begin
      st := st ∪ { NEW_POSITION( M,
                                  GET_POINT_TYPE(pi),
                                  GET_POINT_X(pi),
                                  GET_POINT_Y(pi) ) }
    end
  end

  return( st )
end;

Algorithm:

  1. Convert to POINT: Extract (type, X, Y) from POSITION q
  2. Compute r_n(q, b): Extract relevant substring from bit vector b
  3. Apply $\delta ^D,\chi _e$: deltaED := $\delta ^D,\chi _e$(point, r_n(q, b))
  4. Convert back to POSITIONs:
    • If q is I-type: Shift X by -1 (accounts for parameter offset)
    • If q is M-type: Keep X unchanged
    • Preserve parameter, type, and Y

Key Functions:

  • R(n, q, b): Extracts substring of b (implements r_n)
  • Delta_E_D: Applies deterministic elementary transition (implements $\delta ^D,\chi _e)$

M

Implements m_n(st, k) - converts between I-type and M-type positions (diagonal crossing).

function M( n : INTEGER; st : STATE; k : INTEGER ) : STATE;
(* M(n, st, k) corresponds to m_n(st, k) *)
VAR m  : STATE;
    pi : POSITION;
begin
  m = {};

  for pi in st do begin
    if( GET_POSITION_PARAM(pi) = I ) then begin
      // I → M conversion
      m := m ∪ { NEW_POSITION( M,
                                GET_POSITION_TYPE(pi),
                                GET_POSITION_X(pi) + n + 1 - k,
                                GET_POSITION_Y(pi) ) }
    end
    else begin
      // M → I conversion
      m := m ∪ { NEW_POSITION( I,
                                GET_POSITION_TYPE(pi),
                                GET_POSITION_X(pi) - n - 1 + k,
                                GET_POSITION_Y(pi) ) }
    end
  end

  return( m )
end;

Conversion Formulas (from Definition 17):

I → M:

I + i#e  ↦  M + (i + n + 1 - k)#e
It + i#e ↦  Mt + (i + n + 1 - k)#e
Is + i#e ↦  Ms + (i + n + 1 - k)#e

M → I:

M + i#e  ↦  I + (i - n - 1 + k)#e
Mt + i#e ↦  It + (i - n - 1 + k)#e
Ms + i#e ↦  Is + (i - n - 1 + k)#e

Purpose: Allows positions to "cross the diagonal" when transitioning from $I^\chi _s$ states to $M^\chi _s$ states (and vice versa).

R

Implements r_n(pos, b) - extracts relevant substring from bit vector b.

function R( n : INTEGER; pos : POSITION; b : STRING ) : STRING;
(* R(n, pos, b) corresponds to r_n(pos, b) *)
VAR len : INTEGER;
begin
  if( GET_POSITION_PARAM(pos) = I ) then begin
    // I-type position
    if( n - GET_POSITION_Y(pos) + 1 <
        LENGTH(b) - n - GET_POSITION_X(pos) ) then begin
      len := n - GET_POSITION_Y(pos) + 1
    end
    else begin
      len := LENGTH(b) - n - GET_POSITION_X(pos)
    end
    return( SUB_STRING(b, n + GET_POSITION_X(pos) + 1, len) )
  end

  // M-type position
  if( n - GET_POSITION_Y(pos) + 1 < -GET_POSITION_X(pos) ) then begin
    len := n - GET_POSITION_Y(pos) + 1
  end
  else begin
    len := -GET_POSITION_X(pos)
  end
  return( SUB_STRING(b, LENGTH(b) + GET_POSITION_X(pos) + 1, len) )
end;

Definition (from Section 5, Definition 16):

For position $q \in I^\chi _s \cup M^\chi _s$ and bit vector b of length k:

I-type: r_n(I + i#e, b) = b[n + i + 1 ... min(n + i + (n - e + 1), k)] M-type: r_n(M + i#e, b) = b[k + i + 1 ... min(k + i + (n - e + 1), k)]

Purpose: Extracts the portion of the bit vector b that corresponds to the "active window" around position q, limited by the remaining error budget (n - e).

Length Calculation:

  • Max length: n - e + 1 (error budget limits how far we can look)
  • Actual length: min(max_length, remaining_bits_in_b)

RM

Implements rm(st) - returns the rightmost position in state st.

function RM( st : STATE ) : POSITION;
(* RM(st) corresponds to rm(st) *)
VAR pi, rm : POSITION;
begin
  // Find any "usual" position as starting point
  for pi in st do begin
    if( GET_POSITION_TYPE(pi) = usual ) then begin
      rm := pi
    end
  end

  // Find rightmost: maximize X - Y among "usual" positions
  for pi in st do begin
    if( GET_POSITION_TYPE(pi) = usual and
        GET_POSITION_X(pi) - GET_POSITION_Y(pi) >
        GET_POSITION_X(rm) - GET_POSITION_Y(rm) ) then begin
      rm := pi
    end
  end

  return( rm )
end;

Definition (from Section 4.2):

For state $A \subseteq$ positions:

rm(A) = argmax_{π ∈ A, π is usual type} (X(π) - Y(π))

Purpose: Identifies the "rightmost" position in the state, used to determine diagonal crossing via f_n.

Note: Only considers positions of "usual" type (not t or s subscripts).

F

Implements f_n(pos, k) - checks diagonal crossing condition.

function F( n : INTEGER; pos : POSITION; k : INTEGER ) : BOOLEAN;
(* F(n, pos, k) corresponds to f_n(pos, k) *)
begin
  if( GET_POSITION_PARAM(pos) = I ) then begin
    // I-type: check if close to diagonal
    return( k <= 2*n + 1 and
            GET_POSITION_Y(pos) <= GET_POSITION_X(pos) + 2*n + 1 - k )
  end

  // M-type: check if past diagonal
  return( GET_POSITION_Y(pos) > GET_POSITION_X(pos) + n )
end;

Definition (from Section 5, Definition 16):

f_n(q, k) = {
  (k ≤ 2n+1) ∧ (Y(q) ≤ X(q) + 2n + 1 - k)   if q ∈ I^χ_s
  Y(q) > X(q) + n                              if q ∈ M^χ_s
}

Purpose:

  • I-type: Returns true if position is close enough to diagonal to cross to M-type
  • M-type: Returns true if position is far enough past diagonal to cross back to I-type

Used by: Delta function to determine when to apply m_n conversion

Delta_E_D

Implements $\delta ^D,\chi _e$(pt, h) - deterministic elementary transition on POINTs.

This is the longest and most complex function, implementing all three distance variants $(\varepsilon , t,$ ms).

function Delta_E_D( n : INTEGER; pt : POINT; h : STRING ) : SET_OF_POINTS;
(* Delta_E_D(n, pt, h) corresponds to δ^D,χ_e(pt, h)
   CHI corresponds to the metasymbol χ *)
VAR x, y, j, posOfFirst1 : INTEGER;
begin
  x := GET_POINT_X(pt)
  y := GET_POINT_Y(pt)

  if( CHI = epsilon ) then begin
    // ────────────────────────────────────────────────────────────
    // STANDARD LEVENSHTEIN (ε)
    // ────────────────────────────────────────────────────────────

    if( LENGTH(h) = 0 ) then begin
      // No matches: substitution only
      if( y < n ) then begin
        return( { NEW_POINT(usual, x, y+1) } )
      end
      return( {} )
    end

    if( h[1] = 1 ) then begin
      // First character matches: no error
      return( { NEW_POINT(usual, x+1, y) } )
    end

    if( LENGTH(h) = 1 ) then begin
      // Single mismatch: insertion or substitution
      if( y < n ) then begin
        return( { NEW_POINT(usual, x, y+1),      // substitution
                  NEW_POINT(usual, x+1, y+1) } )  // insertion
      end
      return( {} )
    end

    // h has length ≥ 2, h[1] = 0
    posOfFirst1 := 0;
    for j := 2 to LENGTH(h) do begin
      if( h[j] = 1 ) then begin
        posOfFirst1 := j;
        goto LABEL2
      end
    end

    LABEL2:
    if( posOfFirst1 = 0 ) then begin
      // No match found: substitution + insertion
      return( { NEW_POINT(usual, x, y+1),
                NEW_POINT(usual, x+1, y+1) } )
    end

    // Match found at position j
    return( { NEW_POINT(usual, x, y+1),        // substitution
              NEW_POINT(usual, x+1, y+1),      // insertion
              NEW_POINT(usual, x+j, y+j-1) } ) // deletion(s) then match

  end
  else begin
    if( CHI = t ) then begin
      // ────────────────────────────────────────────────────────────
      // WITH TRANSPOSITION (t)
      // ────────────────────────────────────────────────────────────

      if( GET_POINT_TYPE(pt) = t ) then begin
        // Special transposition state: must complete swap
        if( h[1] = 1 ) then begin
          return( { NEW_POINT(usual, x+2, y) } )
        end
        return( {} )
      end

      // Regular state
      if( LENGTH(h) = 0 ) then begin
        if( y < n ) then begin
          return( { NEW_POINT(usual, x, y+1) } )
        end
        return( {} )
      end

      if( h[1] = 1 ) then begin
        return( { NEW_POINT(usual, x+1, y) } )
      end

      if( LENGTH(h) = 1 ) then begin
        if( y < n ) then begin
          return( { NEW_POINT(usual, x, y+1),
                    NEW_POINT(usual, x+1, y+1) } )
        end
        return( {} )
      end

      if( h[2] = 1 ) then begin
        // Transposition opportunity: h = 0 1 ...
        return( { NEW_POINT(usual, x, y+1),      // substitution
                  NEW_POINT(usual, x+1, y+1),    // insertion
                  NEW_POINT(usual, x+2, y+1),    // deletion
                  NEW_POINT(t, x, y+1) } )       // transposition
      end

      // Search for first match at position j ≥ 3
      posOfFirst1 := 0;
      for j := 3 to LENGTH(h) do begin
        if( h[j] = 1 ) then begin
          posOfFirst1 := j;
          goto LABEL3
        end
      end

      LABEL3:
      if( posOfFirst1 = 0 ) then begin
        return( { NEW_POINT(usual, x, y+1),
                  NEW_POINT(usual, x+1, y+1) } )
      end

      return( { NEW_POINT(usual, x, y+1),
                NEW_POINT(usual, x+1, y+1),
                NEW_POINT(usual, x+j, y+j-1) } )

    end

    // ────────────────────────────────────────────────────────────
    // WITH MERGE/SPLIT (ms)
    // ────────────────────────────────────────────────────────────

    if( GET_POINT_TYPE(pt) = s ) then begin
      // Special split state: must complete split
      return( { NEW_POINT(usual, x+1, y) } )
    end

    // Regular state
    if( LENGTH(h) = 0 ) then begin
      if( y < n ) then begin
        return( { NEW_POINT(usual, x, y+1) } )
      end
      return( {} )
    end

    if( h[1] = 1 ) then begin
      return( { NEW_POINT(usual, x+1, y) } )
    end

    if( LENGTH(h) = 1 ) then begin
      if( y < n ) then begin
        return( { NEW_POINT(usual, x, y+1),
                  NEW_POINT(usual, x+1, y+1),
                  NEW_POINT(s, x, y+1) } )        // split
      end
    end

    return( { NEW_POINT(usual, x, y+1),          // substitution
              NEW_POINT(usual, x+1, y+1),        // insertion
              NEW_POINT(usual, x+2, y+1),        // merge
              NEW_POINT(s, x, y+1) } )           // split
  end
end;

Complexity: This function has variant-specific logic:

Variant: $\varepsilon$ (Standard Levenshtein)

Cases:

  1. |h| = 0: No matches available
    • Substitution: x#(y+1)
  2. h[1] = 1: First character matches
    • Match: (x+1)#y
  3. |h| = 1, h[1] = 0: Single mismatch
    • Substitution: x#(y+1)
    • Insertion: (x+1)#(y+1)
  4. $|h| \ge 2, h[1] = 0$: Look for first match at position j
    • If no match: Substitution + Insertion
    • If match at j: Substitution + Insertion + (Deletion × (j-1) + Match)

Variant: t (With Transposition)

Additional states:

  • Type t position: Waiting to complete transposition
    • If h[1] = 1: Complete swap → (x+2)#y
    • Otherwise: Fail

Cases (for regular positions): 1-4. Same as $\varepsilon$ 5. h = 0 1 ...: Transposition opportunity

  • Substitution, Insertion, Deletion (same as $\varepsilon )$
  • Transposition: Enter type t state at x#(y+1)_t

Variant: ms (With Merge/Split)

Additional states:

  • Type s position: Waiting to complete split
    • Always: (x+1)#y (consume one character)

Cases (for regular positions): 1-3. Same as $\varepsilon$ 4. $|h| \ge 2$:

  • Substitution, Insertion (same as $\varepsilon )$
  • Merge: (x+2)#(y+1) (consume 2 characters for 1 edit)
  • Split: Enter type s state at x#(y+1)_s

6.3 Complexity Analysis

State Count

For $\chi = \varepsilon$ (Standard Levenshtein)

I-type states (non-final):

Define injective function:

f: I^ε_s → [1, 2n+1]
f(I + i#e) = i + e + 1

Then construct:

g: I^ε_states → {0,1,...,2n+1}^(2n+1)

Where for each state $A \in$ $I^\varepsilon _\text{states}$:

g(A)_j = {
  0           if A ∩ A_j = ∅
  f(π)        if π ∈ A ∩ A_j
}

With A_j = $\{I - n + j - 1 - t#(n-t) | 0 \le t \le n\}$.

Key property: g(A) is a strictly increasing sequence (excluding 0s).

Upper bound:

|I^ε_states| ≤ |W|

Where:

W = {w ∈ {0,1,...,2n+1}^(2n+1) | ∀k ∀r < k: (w_k ≠ 0 ⇒ w_k > w_r)}

Calculation:

|W| = Σ_{k=1}^{2n+1} C(2n+1, k)^2
    = C(2(2n+1), 2n+1) - 1
    < [2(2n+1)]! / [(2n+1)! × (2n+1)!]

Using Stirling's formula extension (Robbins 1955, Feller 1968):

√(2πk) k^k e^{-k} e^{1/(12k+1)} < k! < √(2πk) k^k e^{-k} e^{1/(12k)}

We get:

|W| < C × √(2n+1) × (4n+2)^{4n+2} × e^{-(4n+2)} / [(2n+1) × (2n+1)^{4n+2} × e^{-(4n+2)}]

Result:

|I^ε_states| = O(2^{4n - log_2(√(2n+1))})

M-type states (final):

M^ε_states = ⋃_{k=0}^n {A_k}

Where:

A_k = {A | A ∈ M^ε_states ∧ ∃t(0 ≤ t ≤ k ∧ rm(A) = M - k + t#t)}

Properties:

  • |A_k| < |A_n| for all k < n
  • |A_n| < |$I^\varepsilon _\text{states}$|
  • |A_0| = 1

Result:

|M^ε_states| = O(n × 2^{4n - log_2(√(2n+1))})

Total states:

|Q^{∀,ε}_n| = O(n × 2^{4n - log_2(√(2n+1))})
            ≈ O(n × 2^{4n} / √(2n+1))
            = O(4^{2n} × n / √n)
            = O(4^{2n} × √n)

For $\chi = t$ or $\chi =$ ms

Same asymptotic complexity as $\varepsilon$ variant:

|I^{t}_states|  = O(2^{4n - log_2(√(2n+1))})
|M^{t}_states|  = O(n × 2^{4n - log_2(√(2n+1))})

|I^{ms}_states| = O(2^{4n - log_2(√(2n+1))})
|M^{ms}_states| = O(n × 2^{4n - log_2(√(2n+1))})

Reason: Additional position types (t, s) don't increase the asymptotic bound.

Time Complexity

Construction:

  • States: $\mathcal{O}(n \times 4^{2n})$
  • Alphabet size: |$\Sigma ^\forall _n$| = 2^{2n+2} - 2 (bit vectors of length 1 to 2n+2)
  • Transitions per state: At most $|\Sigma ^\forall _n|$
  • Transition computation: Polynomial in n (subsumption checks)

Total construction time:

O(states × alphabet × poly(n))
= O(n × 4^{2n} × 2^{2n+2} × poly(n))
= O(n^k × 4^{4n})  for some constant k

Query time (given $A^\forall ,\chi _n$ and concrete word w):

  • Word length: p = |w|
  • Bit vector encoding: h_n(w, x) computed in $\mathcal{O}(p)$ per character x
  • Traversal: $\mathcal{O}(\lvert x\rvert)$ characters × $\mathcal{O}(2n)$ transitions per character
  • Total: $\mathcal{O}(\lvert x\rvert \times 2n)$ = $\mathcal{O}(\lvert x\rvert \times n)$

Space Complexity

Storage:

  • States: $\mathcal{O}(n \times 4^{2n})$
  • Transitions: $\mathcal{O}(n \times 4^{2n} \times 2^{2n+2})$ = $\mathcal{O}(n \times 4^{4n})$
  • Each state: Set of at most $\mathcal{O}(n^{2})$ positions (from $I^\chi _s \cup M^\chi _s)$
  • Each position: $\mathcal{O}(\log n)$ bits

Total space:

O(states × positions_per_state × bits_per_position)
= O(n × 4^{2n} × n² × log n)
= O(n³ log n × 4^{2n})

6.4 Experimental Results

Note: Section 6.4 contains tables showing actual state counts for $A^\forall ,\chi _n$ at various n values. The thesis pages 58-59 have these tables, but they're primarily empirical data rather than algorithmic content.

Key observations from results:

  1. State counts grow exponentially but remain tractable for $n \le 3$
  2. Transposition (t) and merge/split (ms) variants have slightly more states than standard $(\varepsilon )$
  3. Precomputation is feasible for small n, enabling fast queries

Implementation Notes

Critical Implementation Details

  1. State Representation:

    • Use hash set for STATE (efficient $\in , \cup ,$ $, \cap$ operations)
    • Use hash set for tracking visited states (HAS_NEVER_BEEN_PUSHED)
    • Implement proper equality and hashing for POSITION tuples

  2. Subsumption Closure:

    • Delta function must maintain $\sqcup$ (anti-chain property)
    • Two-phase: remove subsumed, add if not subsumed
    • Critical for keeping states minimal

  3. Bit Vector Encoding:

    • Input alphabet $\Sigma ^\forall _n =$ {0,1}^{1 to 2n+2}
    • For concrete word w: $h_n(w, x) = \beta (x, s_n(w, 1))...\beta (x, s_n(w, |x|))$
    • Precompute characteristic vectors $\beta (x, w)$ for efficiency

  4. Diagonal Crossing:

    • Check f_n(rm(nextSt), |b|) after each transition
    • Apply m_n conversion when crossing
    • Handles I ↔ M parameter changes

  5. Variant Selection:

    • Global CHI variable: epsilon=0, t=1, ms=2
    • Delta_E_D branches on CHI for variant-specific logic
    • Type field distinguishes usual/t/s positions

Optimization Opportunities

  1. Precomputation:

    • Build $A^\forall ,\chi _n$ offline for small $n (n \le 3)$
    • Serialize to disk for fast loading
    • Amortizes $\mathcal{O}(4^{4n})$ construction cost

  2. Caching:

    • Cache $\delta ^\forall ,\chi _e$ results for common (q, b) pairs
    • Cache subsumption checks
    • Cache r_n(q, b) extractions

  3. Bit Vector Operations:

    • Use bitwise operations for $\beta (x, w)$ computation
    • SIMD for parallel bit vector processing
    • Lazy bit vector generation during traversal

  4. State Minimization:

    • Subsumption closure $\sqcup$ already minimizes states
    • No further DFA minimization needed $(A^\forall ,\chi _n$ is already minimal per Section 7)

Testing Strategies

  1. Correctness:

    • Test against reference DFA construction: $A^D,\chi _n(w)$ for concrete w
    • Property: $L(A^\forall ,\chi _n(w)) = L(A^D,\chi _n(w))$ for all w
    • Verify subsumption invariant: all states are anti-chains

  2. Completeness:

    • Verify all states reachable via BFS
    • Check no orphaned states
    • Validate initial state and final states

  3. Complexity:

    • Measure actual state counts vs theoretical bounds
    • Profile transition computation bottlenecks
    • Benchmark query time on real dictionaries

Correspondence to Theoretical Definitions

Algorithm ComponentTheoretical DefinitionSection
Build_AutomatonConstruction of $A^\forall ,\chi _n$Def. 15
Delta$\delta ^\forall ,\chi _n$ transition functionDef. 15
Delta_E$\delta ^\forall ,\chi _e$ elementary transitionDef. 16
Delta_E_D$\delta ^D,\chi _e$ deterministic elementaryDef. 7
Less_Than_Subsume$<^\chi _s$ subsumption relationDef. 11
Mm_n diagonal crossingDef. 17
Ff_n crossing predicateDef. 17
Rr_n substring extractionDef. 16
RMrm rightmost positionDef. 12
Length_Covers_All_The_Positions$k \in \nabla _a$(st) length checkDef. 15

Summary

Section 6 provides a complete, executable specification for building Universal Levenshtein Automata:

Key Achievements:

  1. ✅ BFS construction with cycle handling
  2. ✅ Subsumption closure for state minimization
  3. ✅ All three variants $(\varepsilon , t,$ ms) supported
  4. ✅ Polynomial construction time (though exponential in n)
  5. ✅ $\mathcal{O}(\lvert x\rvert \times n)$ query time for word x

Practical Considerations:

  • Feasible for $n \le 3$ (real-world edit distances)
  • Precomputation recommended
  • Critical for parameter-free fuzzy matching

Next Steps (for implementation):

  1. Implement type system (POSITION, POINT, STATE)
  2. Implement core functions (Delta, Delta_E, Delta_E_D)
  3. Implement subsumption logic (Less_Than_Subsume)
  4. Build BFS loop (Build_Automaton)
  5. Add bit vector encoding h_n for concrete words
  6. Test against reference automata

See Also:

  • PAPER_SUMMARY.md - Complete theoretical foundations
  • GLOSSARY.md - Notation reference
  • Section 7 (Minimality) - Proof that $A^\forall ,\chi _n$ is minimal
  • Section 8 (Properties) - Additional theoretical properties

Document Status: ✅ Complete algorithmic extraction from Section 6 Last Updated: 2025-11-11 Total Lines: 1500+ Coverage: Pages 48-59 of thesis

❮Time Warp Edit Distance: source analysis and implementation contractUniversal Levenshtein Automata - Glossary❯

Can you improve this documentation?Edit on GitHub

cljdoc builds & hosts documentation for Clojure/Script libraries

Keyboard shortcuts
Ctrl+kJump to recent docs
←Move to previous article
→Move to next article
Ctrl+/Jump to the search field
Raise an issueBrowse cljdoc sourceChat on Slack
× close