Phase 4 implements the complete Universal Levenshtein Automaton A^∀,χ_n structure, including initialization, state transitions, bit vector encoding, and word acceptance checking. Most components are implemented correctly, but the acceptance condition requires further work.
src/transducer/universal/automaton.rs (477 lines)src/transducer/universal/mod.rs (added automaton module export)docs/research/universal-levenshtein/PHASE4_BUG_ANALYSIS.mdpub struct UniversalAutomaton<V: PositionVariant> {
max_distance: u8,
_phantom: std::marker::PhantomData<V>,
}
Features:
From thesis page 38: I^∀,χ = {I#0}
fn initial_state(&self) -> UniversalState<V> {
let mut state = UniversalState::new(self.max_distance);
// I#0: I-type position with offset 0, errors 0
if let Ok(pos) = UniversalPosition::new_i(0, 0, self.max_distance) {
state.add_position(pos);
}
state
}
From thesis page 38: F^∀,χ_n = M^χ_states
fn is_final(&self, state: &UniversalState<V>) -> bool {
state.positions().any(|pos| pos.is_m_type())
}
NOTE: This implementation is incomplete - see PHASE4_BUG_ANALYSIS.md for details.
From thesis page 51: s_n(w, i) = w_{i-n}...w_v where v = min(|w|, i+n+1)
fn relevant_subword(&self, word: &str, position: usize) -> String {
let n = self.max_distance as i32;
let i = position as i32;
let start = i - n;
let v = std::cmp::min(word.len() as i32, i + n + 1);
let mut result = String::new();
for pos in start..=v {
if pos < 1 {
result.push('$'); // Padding
} else if pos <= word.len() as i32 {
let idx = (pos - 1) as usize;
if let Some(ch) = word.chars().nth(idx) {
result.push(ch);
}
}
}
result
}
Key Features:
From thesis page 51-52: h_n(w, x) encoding and acceptance
pub fn accepts(&self, word: &str, input: &str) -> bool {
let mut state = self.initial_state();
for (i, input_char) in input.chars().enumerate() {
let subword = self.relevant_subword(word, i + 1);
let bit_vector = CharacteristicVector::new(input_char, &subword);
if let Some(next_state) = state.transition(&bit_vector, i + 1) {
state = next_state;
} else {
return false;
}
}
self.is_final(&state)
}
Algorithm:
ISSUE: Acceptance condition is incomplete - see bug analysis.
Passing: 144 / 154 tests (includes all previous phases)
Failing: 10 acceptance tests
test_accepts_* category failingProblem: Current is_final() only checks for M-type positions, but:
Impact: All acceptance tests fail
Analysis: See PHASE4_BUG_ANALYSIS.md for detailed investigation
Problem: Some transitions fail after 2-3 steps even for identical strings
Debug Output (test_accepts_identical):
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 ✗
Hypothesis: Bit vector length or diagonal crossing causing empty successor states
A^∀,χ_n = ⟨Σ^∀_n, Q^∀,χ_n, I^∀,χ, F^∀,χ_n, δ^∀,χ_n⟩
Where:
s_n(w, i) = w_{i-n}w_{i-n+1}...w_v
where v = min(|w|, i + n + 1)
Purpose: Extract window of at most 2n+2 characters around position i.
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
Purpose: Encode pair (w, x) as bit vector sequence for automaton processing.
UniversalPosition<V> for I-type and M-type positionsUniversalState<V> for state managementCharacteristicVector for bit vector encodingUniversalState::transition() for state transitionsinput_length parameter for diagonal crossinguse liblevenshtein::transducer::universal::{UniversalAutomaton, Standard};
let automaton = UniversalAutomaton::<Standard>::new(2);
assert_eq!(automaton.max_distance(), 2);
let automaton = UniversalAutomaton::<Standard>::new(2);
// Distance 0
assert!(automaton.accepts("test", "test"));
// Distance 1
assert!(automaton.accepts("test", "text")); // substitution
assert!(automaton.accepts("test", "teast")); // insertion
assert!(automaton.accepts("test", "tet")); // deletion
// Distance > 2
assert!(!automaton.accepts("test", "hello"));
let automaton = UniversalAutomaton::<Standard>::new(2);
// Position 1 (n=2): window [-1, 4] = $$test (2 padding + 4 word chars)
let subword = automaton.relevant_subword("test", 1);
assert_eq!(subword, "$$test");
// Position 3 (n=2): window [1, 6] but clamp to [1, 4] = test
let subword = automaton.relevant_subword("test", 3);
assert_eq!(subword, "test");
Phase 4 successfully implements most of the Universal Levenshtein Automaton:
✓ Automaton structure (UniversalAutomaton) ✓ Initial state generation ({I#0}) ✓ Relevant subword computation (s_n function) ✓ Bit vector encoding per input character ✓ State transition loop (uses Phase 2 Week 5 transition) ✓ 144 tests passing (including all previous phases)
❌ Acceptance condition incomplete (10 tests failing) ❌ Transitions failing for some inputs (needs investigation)
The foundation is solid and most components are correct. The remaining work is to fix the acceptance logic and debug the transition failures. Once these are resolved, Phase 4 will be complete.
Completion Date: 2025-11-11 (in progress) Tests Passing: 144 / 154 Status: 🚧 INCOMPLETE (acceptance condition needs fix)
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 |