wiki_research

commit 080dbcfffa0aab9f6d52fe49064b7ba5993ae41b
parent da2b33a1ffb7001e20710bedb8f399df5eede914
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 14 Jan 2025 17:47:59 +0100

commit with codex

Diffstat:
decision_problem
 | 
2
+-
simons_congruence
 | 
9
+++++++++
subsequence
 | 
2
++
subsequence_universal_word
 | 
9
+++++++++
subword_universal
 | 
4
++--
universal_word
 | 
2
+-

6 files changed, 24 insertions(+), 4 deletions(-)
diff --git a/decision_problem b/decision_problem
@@ -6,4 +6,4 @@ Up: [computational_problem], [boolean]
 
 See also: [decision], [decidability]
 
-Aliases: decision problems
+Aliases: decision problems, decide
diff --git a/simons_congruence b/simons_congruence
@@ -0,0 +1,9 @@
+# Simons congruence
+
+Two [words] are [equivalent] for *Simon's congruence* if they have the same set of [subsequences] of length k
+
+See for instance [adamson2023ranking]
+
+Up: [formal_language_theory]
+
+See also: [subsequence_universal_word]
diff --git a/subsequence b/subsequence
@@ -19,3 +19,5 @@
 See also: [subword], [sequence], [subword]
 
 Up: [formal_language_theory], [stringology]
+
+Aliases: subsequences
diff --git a/subsequence_universal_word b/subsequence_universal_word
@@ -0,0 +1,9 @@
+# Subsequence universal word
+
+A [word] is *k-subsequence-universal* if it contains all possible [words] of length k as a [subsequence]
+
+See for instance [adamson2023ranking]
+
+Up: [word], [word_combinatorics]
+
+See also: [universal_word], [simons_congruence]
diff --git a/subword_universal b/subword_universal
@@ -1,8 +1,8 @@
 # Subword universal
 
-[automata] where every [word] is a [subword] of an accepted word
+An [automaton] is *subword-universal* if every possible [word] is a [subword] of an accepted word
 
-can determine in [ptime] if [automata_nondeterministic] is subword-universal
+can [decide] in [ptime] if [automata_nondeterministic] is subword-universal
   - cf [rampersad2009computational] Theorem 12
 
 Up: [universality_automata]
diff --git a/universal_word b/universal_word
@@ -6,6 +6,6 @@
 - always exists for any alphabet and length
 - cf [chung1992universal]
 
-See also: [superpermutation], [random_universal_word], [de_bruijn_sequence], [universal_tree]
+See also: [superpermutation], [random_universal_word], [de_bruijn_sequence], [universal_tree], [subsequence_universal_word]
 
 Up: [word], [word_combinatorics]