commit 6e0e32558603b9dc735475a4e3cd2da9e5491321
parent 46cd9cd64424192521734656b300c20ce055d3e6
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 2 Sep 2025 10:47:40 +0200
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
19 files changed, 66 insertions(+), 13 deletions(-)
diff --git a/automata b/automata
@@ -14,3 +14,5 @@ https://en.wikipedia.org/wiki/Finite-state_machine
Up: [theoretical_computer_science], [formal_language_theory]
Aliases: automaton
+
+See also: [cellular_automata]
diff --git a/brzozowskis_algorithm b/brzozowskis_algorithm
@@ -1,5 +1,7 @@
# Brzozowski's algorithm
+https://fr.wikipedia.org/wiki/Algorithme_de_Brzozowski_de_minimisation_d%27un_automate_fini
+
[Algorithm] for [automaton_minimization].
Take [automaton_mirror] then [determinize] then take [automaton_mirror] then [determinize]
@@ -7,4 +9,4 @@ Take [automaton_mirror] then [determinize] then take [automaton_mirror] then [de
- [complexity_generic] studied in [defeclice2013brzozowski]:
- [super_polynomial] on [automata_random]
-Up: [minimization_automaton]
+Up: [minimization_DFAs]
diff --git a/database_theory_concepts b/database_theory_concepts
@@ -12,5 +12,7 @@
- [omqa]
- [omqa_finite] vs [omqa_unrestricted]
- [tuple]
+- [fact]
+- [atom]
Up: [database_theory]
diff --git a/dfa_minimization b/dfa_minimization
@@ -0,0 +1,9 @@
+# DFA minimization
+
+- [brzozowskis_algorithm]
+- [hopcrofts_algorithm]
+- [moores_algorithm]
+
+Up: [minimization_automaton] of [DFA]
+
+Aliases: minimization DFAs
diff --git a/enumeration b/enumeration
@@ -22,4 +22,6 @@ https://en.wikipedia.org/wiki/Enumeration_algorithm
- [enumeration_ordered]
- [incremental_maintenance_enumeration]
-Up: [research_directions]
+Up: [algorithms]
+
+Aliases: enumeration algorithms, enumeration algorithm
diff --git a/equivalence_class b/equivalence_class
@@ -0,0 +1,7 @@
+# Equivalence class
+
+A set of elements that are related by an [equivalence_relation]. Forms a [partition] of the set
+
+Up: [equivalence_relation]
+
+Aliases: equivalence classes
diff --git a/formal_language_theory b/formal_language_theory
@@ -53,6 +53,7 @@ Studies [formal_languages]
- [ogdens_lemma]
- [interchange_lemma] https://en.wikipedia.org/wiki/Interchange_lemma
- other such results: https://cstheory.stackexchange.com/a/54032
+- [myhill_nerode_theorem]
Up: [theoretical_computer_science]
diff --git a/hopcrofts_algorithm b/hopcrofts_algorithm
@@ -10,6 +10,6 @@ most efficient known algorithm:
- for n the number of [states] of the [automaton]
- and s the [alphabet] size
-Up: [minimization_automaton]
+Up: [minimization_DFAs]
See also: [Moore's_algorithm]
diff --git a/integrity_constraint b/integrity_constraint
@@ -1,5 +1,16 @@
# Integrity constraint
+## Notions
+
+- [satisfaction] of an integrity constraint by a database
+
+## [computational_problems]
+
+- [entailment]
+- [database_repairs]
+
+## Types
+
- [database_dependency]
- [equality_generating_dependency]
- [functional_dependency]
diff --git a/logic b/logic
@@ -20,6 +20,7 @@
- [separator_logic]
- [description_logics]
- [LTL]
+- [logic_alternative]
## Problems
diff --git a/minimization_automaton b/minimization_automaton
@@ -1,12 +1,9 @@
# Minimization automaton
-- [brzozowskis_algorithm]
- - https://fr.wikipedia.org/wiki/Algorithme_de_Brzozowski_de_minimisation_d%27un_automate_fini
-- [hopcrofts_algorithm]
-- [moores_algorithm]
+- for [DFAs]: [DFA_minimization]
- for [NFAs]: [NFA_minimization]
-Up: [minimization]
+Up: [minimization] of [automaton]
Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata, automaton minimal, minimal automaton
diff --git a/moores_algorithm b/moores_algorithm
@@ -4,6 +4,6 @@ https://fr.wikipedia.org/wiki/Algorithme_de_Moore_de_minimisation_d%27un_automat
Constructs [myhill_nerode_equivalence] by successive refinement from the partition of states into [final_states] and [nonfinal_states]
-Up: [minimization_automaton]
+Up: [minimization_DFAs]
See also: [hopcrofts_algorithm]
diff --git a/myhill_nerode_equivalence b/myhill_nerode_equivalence
@@ -7,4 +7,4 @@ This is similar to [syntactic_congruence] but it only considers [right_extension
Up: [dagstuhl_regular_expressions_matching_indexing_nicola]
-See also: [syntactic_congruence], [automaton_minimization]
+See also: [syntactic_congruence], [automaton_minimization], [myhill_nerode_theorem]
diff --git a/myhill_nerode_theorem b/myhill_nerode_theorem
@@ -0,0 +1,9 @@
+# Myhill nerode theorem
+
+https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
+
+The [theorem] that says that a [formal_language] is a [regular_language] iff the [Myhill_nerode_equivalence] has a finite number of [equivalence_classes]
+
+Up: [formal_language_theory]
+
+See also: [Myhill_nerode_equivalence], [DFA_minimization]
diff --git a/primary_key b/primary_key
@@ -2,7 +2,11 @@
A set of [attributes] which [functionally_determines] all other [attributes]. It can be expressed as [functional_dependencies], and it is a special case of them
+It has an [arity]
+
- [primary_key_simple], which consists of a single [attribute]
- like [unary_functional_dependencies]
Up: [functional_dependency]
+
+Aliases: key dependency, key dependencies, KDs
diff --git a/randomness b/randomness
@@ -15,6 +15,6 @@
Up: [mathematics]
-See also: [probabilities]
+See also: [probabilities], [chaos]
Aliases: random
diff --git a/rpq_simple_paths b/rpq_simple_paths
@@ -10,4 +10,4 @@ For instance:
Up: [rpq_semantics], [RPQ], [simple_paths]
-Aliases: RPQ simple path
+Aliases: RPQ simple path, simple path RPQ, simple path RPQs
diff --git a/tuple_generating_dependency b/tuple_generating_dependency
@@ -4,6 +4,12 @@
Also called "existential rules", see [existential_rules]
+## Notions
+
+- [trigger]
+ - [trigger_active]
+- [satisfaction] of a TGD by a database
+
## [Academic_papers]
- [zhang2021characterizing]: [expressiveness] of [OMQA] in various formalisms
diff --git a/turing_machine b/turing_machine
@@ -23,6 +23,6 @@
Up: [theoretical_computer_science]
-See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity]
+See also: [ram_model], [church_turing_thesis], [alan_turing], [pushdown_automaton], [turing_complete], [decidability], [recursively_enumerable], [kolmogorov_complexity], [busy_beaver]
Aliases: Turing machines
