commit 537ed7047b032dcdcd6369c050ba2082fdea772b parent 168c85705b999bd16f9b209020f6fbab62d79ed1 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]