commit 4ea92467b8d880bf5202001f394d18118fa48e69 parent 22e3801e3431e91754d1ab08137de607a197efa2 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Mon, 30 Jun 2025 19:54:29 +0200 commit with codex Diffstat:
| subsequence_automaton | | | 9 | +++++++++ |
1 file changed, 9 insertions(+), 0 deletions(-)
diff --git a/subsequence_automaton b/subsequence_automaton @@ -0,0 +1,9 @@ +# Subsequence automaton + +A *subsequence [automaton]* for a [word] w is an [automaton] A that accepts precisely the [formal_language] of all [subsequences] of w, i.e., the [downwards_closure] of the [singleton_language] {w} + +[Computational_problem]: Given a [word] w, we can [greedily] build a [DFA] subsequence automaton: stated as Observation 1 of [hofman2015separability] + +Up: [subsequence] + +See also: [common_subsequence_automaton], [downwards_closure]