String edit distance through the lens of AI planning using Answer Set Programming (ASP). Rather than diving into yet another dynamic programming solution, we'll explore transformation sequences as planning problems.
Rather than diving into yet another dynamic programming solution to string edit distance, let's look at it through a completely different lens — as an AI planning problem. While most developers think of edit distance as "how many changes do I need to make?", we'll ask "what sequence of actions transforms one string into another?"Answer Set Programming (ASP) gives us a powerful way to explore this perspective. Instead of writing algorithms to compute distances, we'll declare the rules of string transformation and let ASP discover optimal edit sequences. By expressing string operations as logical actions that evolve state over time, we gain deep insights into the nature of string similarity itself.
Setting the Stage
The traditional view of edit distance focuses on counting operations — insertions, deletions, and substitutions. But let's reframe this as a planning problem where we:
Start with an initial string state
Have a goal string we want to reach
Can perform discrete transformation actions
Want to find the shortest path between states
This shift from "counting differences" to "planning transformations" isn't just philosophical — it opens up powerful new ways to reason about string operations. Instead of asking "how different are these strings?", we ask "how do we get from one to the other?"The beauty of this approach is that it matches how humans actually think about string transformations. When we see "cat" and want to get to "bat", we don't calculate edit matrices — we think "change the 'c' to a 'b'". ASP lets us express these intuitive operations directly while automatically handling all the complex state management.
char(1, a) .
char(2, b) .
char(3, c) .
char(4, nil) .
The non-character nil is used to indicate an empty position.
Length
In this example there are at most 4 positions (the length of the longest string):
#const length = 4 .
We leave it as an exercise for the reader to derive this constant from the max of the input and goal strings.
Horizon
For sanity, it's always best to define the horizon even if the value is explicit set each time the program is run. It informs the reader that the symbol is in fact a constant.
#const horizon = 3 .
Some convenience predicates:
next(I) ← I = 0..horizon-1 .
always(I) ← I = 0..horizon .
Core Rules
Inertia: a Character exists in its Position unless something changes it. Specifically, if a Character exists in its Position at an Instant then it may or may not be there at the next Instant
{ charΔ(P, C, I+1) } ← charΔ(P, C, I), next(I) .
Uniqueness / Existence: there can be one and only one Character per Position at each Instant
nil can only occur at the end of the string. Specifically, it cannot be that nil occurs in a Position where the Character to the right of it is notnil (accounting for the length of the string):
ASP: This is one of those "aha!" moments that shows the true power of ASP's declarative approach. Rather than painstakingly listing every valid string configuration or writing complex algorithms to generate them, we simply:
Say what characters are allowed (allowed(a ; nil))
Use a choice rule to put exactly one character in each position
Let our nil constraint filter out invalid combinations
The magic is that ASP automatically explores all possible combinations, keeping only those that satisfy our rules. We don't need to think about the combinatorics or edge cases — ASP handles all that complexity behind the scenes.This pattern of "generate and test" is a key ASP idiom:
Generate: Use choice rules to create potential solutions
Test: Use constraints to eliminate invalid ones
It's like having a tireless assistant who tries every possibility while ensuring all our rules are followed. This approach often leads to surprisingly concise and powerful solutions that would be much more complex to express imperatively.
Actions
Substitution: substituteΩ/3
Substitution is the easiest action to encode since it is simply changing the value of a single Position:
Insertion at a Position means that all Characters at Positions greater than the insertion Position are moved one Position to the right (i.e. to the next larger Position):
and that the desired Character is inserted at the Position:
charΔ(P, C, I+1) ←
insertΩ(P, C, I),
next(I) .
(Note that substituteΩ/3could be used in this case.) This implies that the last Position (length) must be empty (contain nil) otherwise Insertion cannot occur.
We'll leave it an an exercise for the reader to express the previous constraint in terms of the current length of the String (meaning the number of positions that are not nil).Prevent inserting in a nil value
⊥ ← insertΩ(_, nil, I),
always(I) .
Unit Tests
One cannot insert if there are no available Positions:
insertΩ(1, x, 0) .
{Unsatisfiable}
Insertion works as expected in the various Positions:
Deleting a Character at a Position means that all Characters at Positions greater than the Deletion Position are moved one Position to the left (i.e. to the next smaller Position):
Now that all of the actions exist, we simply need to generate all possible Actions that results in the final state char/2 and ASP will return only those that are valid:
An important implementation note: while our example conveniently uses characters that exist in both strings, the general case would need to handle insertions of any valid character. This is why our choice rule for generating plans allows inserting any character from the goal state, not just those present in the initial string. For a complete solution, we would define the full alphabet of valid characters that can be used.
Now comes the fascinating part — discovering the minimal sequence of actions needed to transform our string. Rather than diving straight into complex optimization, let's take a systematic approach by exploring increasingly longer sequences until we find a valid solution.Let's walk through this exploration step by step:
With horizon=1, we only have time for a single action. Can we transform "dccb" into "abc" with just one operation? ASP tells us
{Unsatisfiable}
— clearly impossible!
At horizon=2, we have two actions to work with. Still
{Unsatisfiable}
— the gap between our strings is too large to bridge with just two operations.
At horizon=3, we get our first solutions! ASP finds several valid three-step sequences that achieve our goal. Here's one of the six possible solutions:
{
i
deleteΩ/2
substituteΩ/3
0 → 1
2
b
1 → 2
1
a
2 → 3
4
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
b
3
c
4
b
2
1
a
2
b
3
c
4
b
3
1
a
2
b
3
c
4
nil
}
Substitute 'b' for 'c' at position 2
Substitute 'a' for 'd' at position 1
Delete the final 'b' (at position 4)
Just for completeness, checking horizon=4 reveals additional valid (but longer) paths.
{
i
deleteΩ/2
substituteΩ/3
0 → 1
2
b
1 → 2
2
b
2 → 3
4
3 → 4
1
a
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
b
3
c
4
b
2
1
d
2
b
3
c
4
b
3
1
d
2
b
3
c
4
nil
4
1
a
2
b
3
c
4
nil
}{
i
deleteΩ/2
substituteΩ/3
0 → 1
2
b
1 → 2
3
c
2 → 3
4
3 → 4
1
a
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
b
3
c
4
b
2
1
d
2
b
3
c
4
b
3
1
d
2
b
3
c
4
nil
4
1
a
2
b
3
c
4
nil
}{
i
deleteΩ/2
substituteΩ/3
0 → 1
3
c
1 → 2
2
b
2 → 3
4
3 → 4
1
a
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
c
3
c
4
b
2
1
d
2
b
3
c
4
b
3
1
d
2
b
3
c
4
nil
4
1
a
2
b
3
c
4
nil
}{
i
deleteΩ/2
substituteΩ/3
0 → 1
2
b
1 → 2
1
a
2 → 3
4
3 → 4
1
a
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
b
3
c
4
b
2
1
a
2
b
3
c
4
b
3
1
a
2
b
3
c
4
nil
4
1
a
2
b
3
c
4
nil
}{
i
deleteΩ/2
substituteΩ/3
0 → 1
3
c
1 → 2
4
2 → 3
2
b
3 → 4
1
a
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
c
3
c
4
b
2
1
d
2
c
3
c
4
nil
3
1
d
2
b
3
c
4
nil
4
1
a
2
b
3
c
4
nil
}
…
This systematic exploration reveals something profound — we've not just found a solution, we've found the shortest possible solution. Any sequence that transforms "dccb" to "abc" must use at least 3 operations.The beauty of this approach is that when ASP finds a solution at horizon N, we know with mathematical certainty that no solution exists with fewer steps. It's like having a proof of optimality built into our exploration process.
Let's Have Some Fun!
Now that we have fully defined our search space through ASP constraints, we can use this framework as a playground for exploring interesting string transformation scenarios. Rather than just finding paths between specific strings, we can pose creative "what-if" questions about the nature of string edit operations themselves.
What-If Analysis
One particularly interesting question we can ask: given our three fundamental operations (substituteΩ/3, insertΩ/3, deleteΩ/2), what initial strings could be transformed into a target string using exactly one of each operation? This isn't just about finding a path between strings — it's about understanding the structural properties of string transformations themselves.Allowed characters:
We can talk to our friendly neighborhood LLM who happens to be a specialist in ASP for some insights:
Rob What do you notice about the results with horizon=4 in the "Goal Case" section? What rules would you propose to make a more meaningful result?LARE (Asp Specialist)Upon observing the results with horizon=4, we notice that there are multiple valid plans that achieve the goal, but some plans contain unnecessary actions. For instance, a character might be substituted multiple times even when it is not required, or deletions and substitutions are performed in an order that is not the most efficient. To refine the results and guide the solver towards more meaningful and efficient plans, we can introduce the following rules:
Minimize the number of actions: Introduce a minimization statement that instructs the solver to prefer plans with fewer actions.
#minimize{ 1@1, P, I : substituteΩ(P, _, I) ;
1@1, P, I : insertΩ(P, _, I) ;
1@1, P, I : deleteΩ(P, I) } .
{
i
deleteΩ/2
substituteΩ/3
0 → 1
1
a
1 → 2
2
b
2 → 3
4
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
a
2
c
3
c
4
b
2
1
a
2
b
3
c
4
b
3
1
a
2
b
3
c
4
nil
}
Sequential Action Application: Ensure that substitutions happen before insertions and deletions, as they are less disruptive to the string structure. This can be done by assigning different weights to actions, with substitutions having the lowest weight.
#minimize{ 1@1, P, I : substituteΩ(P, _, I) ;
2@2, P, I : insertΩ(P, _, I) ;
3@3, P, I : deleteΩ(P, I) } .
{
i
deleteΩ/2
substituteΩ/3
0 → 1
2
b
1 → 2
2
b
2 → 3
4
3 → 4
1
a
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
b
3
c
4
b
2
1
d
2
b
3
c
4
b
3
1
d
2
b
3
c
4
nil
4
1
a
2
b
3
c
4
nil
}
Avoid Redundant Substitutions: Add constraints to prevent substituting a character with itself, which is an unnecessary action.
Action Prerequisites: Introduce rules that enforce logical prerequisites for actions, such as not allowing a deletion or insertion in positions that have already been set to the goal state in a previous step, thereby preventing redundant or contradictory actions.
By incorporating these additional rules, we guide the solver to generate more parsimonious plans and eliminate plans that contain redundant or unnecessary actions. This will result in a more concise and meaningful set of solutions for the given horizon.
Rob What if we allow our generation to have steps with no actions (to allow for longer horizons):
but we require that an action must occur at Instant I if an action occurred at Instant I+1? We still want to allow for shorter plans (meaning that there may be trailing Instants in which no action occurs).LARE (Asp Specialist)To ensure that an action occurs at Instant I if an action occurred at Instant I+1, while still allowing for shorter plans with possible trailing Instants with no actions, we can introduce a constraint that enforces a dependency between consecutive Instants. Such a constraint would ensure that if an Instant I+1 has an action, then the preceding Instant I must also have an action.Here's an example of how we might encode this requirement:
Ensure that if there is an action at I+1, there must be an action at I
If there is a subsequent action, ensure there was an action at the previous Instant
⊥ ← action_occurred(I+1), not action_occurred(I), next(I).
This constraint does not prevent shorter plans with trailing inaction because it only looks backward from an Instant with an action, not forward from an Instant without one. Thus, if the goal state is reached before the horizon, no further actions are required in the remaining steps.The action_occurred/1 predicate captures the occurrence of any action at a given Instant, making it easier to state the constraint without referring to each action type individually. The constraint then uses this predicate to enforce the required action dependency between consecutive Instants. This approach maintains flexibility for the solver to find the shortest plan necessary to reach the goal state while ensuring logical consistency across the timeline of actions.
{
i
deleteΩ/2
substituteΩ/3
0 → 1
3
1 → 2
1
a
2 → 3
2
b
3 → 4
3
c
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
c
3
b
4
nil
2
1
a
2
c
3
b
4
nil
3
1
a
2
b
3
b
4
nil
4
1
a
2
b
3
c
4
nil
}{
i
deleteΩ/2
substituteΩ/3
0 → 1
2
b
1 → 2
4
2 → 3
1
a
i
charΔ/3
0
1
d
2
c
3
c
4
b
1
1
d
2
b
3
c
4
b
2
1
d
2
b
3
c
4
nil
3
1
a
2
b
3
c
4
nil
4
1
a
2
b
3
c
4
nil
}
The End is Just the Beginning
Our journey through string edit distance has revealed something profound: by reframing classic algorithms as planning problems, we gain powerful new ways to reason about computation. Through ASP's declarative lens, we've transformed string manipulation from a mechanical sequence of operations into an elegant exploration of possibility spaces.What makes this approach particularly powerful is how it separates:
What we want to achieve (our goal state)
How we might get there (our available actions)
Which path is best (our optimization criteria)
This separation of concerns lets us focus on expressing the fundamental rules of string transformation without getting lost in implementation details. Rather than writing algorithms to find edit sequences, we declare the rules of our universe and let ASP discover optimal solutions.But the real power comes from the questions we can now ask:
What initial strings could reach our target with exactly one of each operation?
How do different constraints on action ordering affect possible solutions?
What patterns emerge when we optimize for different criteria?
Each question becomes a small modification to our model rather than a complete rewrite of an algorithm. This flexibility to explore "what-if" scenarios is perhaps ASP's greatest strength — it turns our formal model into a laboratory for discovering insights about the nature of string operations themselves.So go forth and explore! Add new constraints, try different optimizations, push the boundaries of what's possible. The beauty of declarative modeling is that each new rule adds another dimension to our understanding rather than another layer of complexity to manage.After all, in the world of ASP, the end of one exploration is just the beginning of another. What will you discover next?
Reification ("the process of turning a predicate or statement into an addressable object. Reification allows the representation of assertions so that they can be referred to or qualified by other assertions, i.e., meta-knowledge.")
Ordered trees, represented by Depth-First Search (DFS) sequences, bridge the gap between hierarchical and sequential data, enabling precise comparisons and manipulation.14 January 2025
Every story lives first in the space between possibility and form, waiting for rules to shape it. Through Answer Set Programming (ASP), we'll turn logic into narrative, where each constraint becomes a brushstroke in a living world.18 January 2025
