Skip to content

Instantly share code, notes, and snippets.

@DRMacIver

DRMacIver/shortlexpred.md

Last active July 3, 2020 12:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save DRMacIver/89a7a27b70bbb795748fd20d1ad50f82 to your computer and use it in GitHub Desktop.
Save DRMacIver/89a7a27b70bbb795748fd20d1ad50f82 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
shortlexpred.md

Finding the shortlex predecessor

Problem: You have a DFA M and a string s that matches it. You want to find the shortlex-predecessor to s in the language matched by the DFA.

Solution:

Create the P which matches all strings that are strictly shortlex smaller than s. Build the product DFA M' which intersects M with P, matching all strings matched by M that are shortlex predecessors of s.

Now annotate each state in M' with the length of the longest matching string starting from there (this is possible because there is an upper bound on the length of strings matched by M' and is easy to calculate recursively with dynamic programming because this means there are no loops in the DFA).

Walk the DFA as follows: At each state, pick the largest character that leads to a state whose annotation is one smaller than the annotation of the current state. Stop when you reach a state that is annotated 0. The answer is the sequence of characters you've picked so far.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment