Phase 4: Automaton Acceptance Bug Analysis

Issue Summary

The UniversalAutomaton::accepts() implementation is failing all acceptance tests. The automaton structure and bit vector encoding appear correct, but the acceptance condition is not properly implemented.

Symptoms

Test: test_accepts_empty_to_empty

Word: ""
Input: ""
Expected: true (distance = 0)
Actual: false

Debug output:
- Initial state: {I#0} (1 position)
- No input to process
- Final state: {I#0} (still 1 I-type position)
- is_final() returns false (no M-type positions)

Test: test_accepts_identical

Word: "test"
Input: "test"
Expected: true (distance = 0)
Actual: false

Debug output:
- Step 1: subword="$$test" (6 chars), next_state: 3 positions ✓
- Step 2: subword="$test" (5 chars), next_state: 3 positions ✓
- Step 3: subword="test" (4 chars), transition FAILED ✗

Root Cause Analysis

Problem 1: Empty Word Acceptance

For empty word with empty input:

• Initial state: {I#0} (I-type, offset 0, errors 0)
• No transitions (no input characters)
• Current acceptance check: state.contains(M-type) → false
• Issue: I#0 for empty word should be accepting!

Reason: For an empty word (length 0), being at position 0 with 0 errors means we've successfully matched the entire word. The position I#0 represents "at the start of the word", but for an empty word, start = end.

Problem 2: Transition Failures

For non-empty words, transitions are failing after 2-3 steps.

Possible causes:

1. Bit vector length mismatch with position expectations
2. Diagonal crossing producing empty states
3. Subsumption removing all positions
4. Position offset/error invariants being violated

Problem 3: Acceptance Condition

Current implementation:

fn is_final(&self, state: &UniversalState<V>) -> bool {
    state.positions().any(|pos| pos.is_m_type())
}

This checks if the state contains any M-type position. But this might be:

• Too strict: Rejects valid I-type final positions
• Too lenient: Accepts M-type positions that aren't actually at word end

Thesis Analysis

From Page 38: Final States

F^∀,χ_n = M^χ_states

Final states are those in M^χ_states (containing M-type positions).

From Page 33: M-type Position Set

M^ε_s = {M + t#k | k ≥ -t - n ∧ -2n ≤ t ≤ 0 ∧ 0 ≤ k ≤ n}

M-type positions have:

• Offset t ∈ [-2n, 0] (negative or zero)
• Errors k ≥ -t - n

This means M-type positions represent being "past" the word end.

From Page 51-52: Encoding h_n(w, x)

h_n(w, x₁x₂...x_t) = β(x₁, s_n(w,1))β(x₂, s_n(w,2))...β(x_t, s_n(w,t))

Valid only if t ≤ |w| + n

The encoding processes t input characters against word w.

Key Insight

The automaton processes exactly t characters of input, where t is the input length. After processing:

• If we're in an M-type state: we've consumed more than the word length (insertions or past end)
• If we're in an I-type state: we're still within the word boundaries

But the acceptance should depend on whether we've successfully matched the entire word within the error budget!

Hypothesis: Missing End-of-Word Handling

The thesis automaton A^∀,χ_n is designed to work with the encoding h_n(w, x), which processes exactly |x| input characters. But:

1. If |x| < |w|: We need to "delete" the remaining word characters
2. If |x| = |w|: We should be at or past the word end
3. If |x| > |w|: We've "inserted" extra characters

The current implementation processes all input characters but doesn't handle the case where we need to consume remaining word characters (via deletions).

Proposed Fixes

Fix 1: Special Case for Empty Word

pub fn accepts(&self, word: &str, input: &str) -> bool {
    // Special case: empty word
    if word.is_empty() {
        return input.len() <= self.max_distance as usize;
    }

    // ... rest of implementation
}

Fix 2: Relaxed Acceptance Condition

After processing all input, accept if:

1. State contains M-type position (past word end), OR
2. State contains I-type position within n deletions of word end

fn is_accepting(&self, state: &UniversalState<V>, word_len: usize) -> bool {
    state.positions().any(|pos| {
        if pos.is_m_type() {
            // M-type: past word end
            true
        } else {
            // I-type: check if within n deletions of end
            let offset = pos.offset();
            let errors = pos.errors();
            let remaining = word_len as i32 - offset;
            remaining >= 0 && (errors + remaining as u8) <= self.max_distance
        }
    })
}

Fix 3: Add End-of-Word Transition

After processing all input, simulate deleting remaining word characters:

// After processing all input
for _ in 0..(word.len() - input.len()) {
    // Simulate deletion transitions
    // This would require implementing a special "epsilon" transition
}

Next Steps

1. Re-read thesis sections 4.3-4.4 on connection to fixed-word automata
2. Understand the exact acceptance condition from the simulation lemma
3. Check if there are examples in the thesis showing acceptance traces
4. Implement and test the most appropriate fix
5. Verify against all test cases

References

• Thesis Page 30: Definition 15 (A^∀,χ_n structure)
• Thesis Page 33-36: M-type position sets
• Thesis Page 38: State sets and final states
• Thesis Page 48-50: Complete automata diagrams
• Thesis Page 51-56: Connection to fixed-word automata
• Thesis Page 54: Simulation Lemma 11

---

Status: Under investigation Priority: High (blocks Phase 4 completion) Created: 2025-11-11