wiki_research

commit 18bc8d81f3c52b22b0000361e0b3fa58682ec743
parent edb1ea6fc1e6dbd12e434beb8dab088adec71ed1
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Fri, 24 Jan 2025 17:17:14 +0100

commit with codex

Diffstat:
automata_constructions
 | 
1
+
automata_nondeterministic
 | 
2
+-
context_free_grammar
 | 
4
++++
derivation_tree
 | 
6
+++++-
equivalence_relation
 | 
7
+++++++
learning_dfa
 | 
2
++
mathematics
 | 
1
+
nondeterministic
 | 
4
++--
optimization
 | 
2
+-
tree
 | 
3
++-
tree_labeled
 | 
9
+++++++++
tree_language
 | 
2
+-
word
 | 
2
+-

13 files changed, 37 insertions(+), 8 deletions(-)
diff --git a/automata_constructions b/automata_constructions
@@ -6,6 +6,7 @@
 - [automata_reversal], does not preserve [automata_determistic]
 - [automata_complementation]
 - [product_automaton], for [automaton_intersection]
+- [automata_trimming] / [automata_completion]
 
 Up: [automata]
 
diff --git a/automata_nondeterministic b/automata_nondeterministic
@@ -10,4 +10,4 @@ Up: [nondeterministic], [automata_types]
 
 See also: [epsilon_transition]
 
-Aliases: nondeterministic automaton, nondeterministic automata, NFA, NFAs
+Aliases: nondeterministic automaton, nondeterministic automata, NFA, NFAs, automaton nondeterministic
diff --git a/context_free_grammar b/context_free_grammar
@@ -35,6 +35,10 @@
 
 - [parsing]
 
+## Extensions
+
+- [probabilistic_grammar]
+
 See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series]
 
 Up: [formal_language_theory]
diff --git a/derivation_tree b/derivation_tree
@@ -2,8 +2,12 @@
 
 A derivation tree is a notion of a [context_free_grammar]
 
-The [yield] of a derivation tree is the sequence of its leaves
+The [yield] of a derivation tree is the sequence of its [leaves]
 
 The notion of derivation trees also occurs in [datalog]: [derivation_tree_datalog]
 
 Up: [tree] for [context_free_grammar]
+
+Aliases: parse tree, derivation trees, parse trees
+
+See also: [abstract_syntax_tree]
diff --git a/equivalence_relation b/equivalence_relation
@@ -0,0 +1,7 @@
+# Equivalence relation
+
+A [mathematics_relation] is an equivalence relation if it is [relation_symmetric], [relation_reflexive], and [relation_transitive]
+
+Up: [mathematics]
+
+See also: [equivalence_class], [quotient]
diff --git a/learning_dfa b/learning_dfa
@@ -15,3 +15,5 @@ Also [lingg2024learning] on binary alphabets
 Up: [machine_learning], [automaton]
 
 Aliases: DFA learning
+
+See also: [specification]
diff --git a/mathematics b/mathematics
@@ -35,6 +35,7 @@
 - [plane_mathematics]
 - [modulo]
 - [relation_mathematics]
+- [integer]
 
 ## Notions
 
diff --git a/nondeterministic b/nondeterministic
@@ -1,7 +1,7 @@
 # Nondeterministic
 
-- [automata]
-- [tree_automaton]
+- [automata]: [automaton_nondeterministic]
+- [tree_automaton]: [tree_automaton_nondeterministic]
 - [turing_machine]
 - [degree_of_ambiguity]
 
diff --git a/optimization b/optimization
@@ -11,4 +11,4 @@
 
 Up: [computer_science]
 
-See also: [inefficiency]
+See also: [inefficiency], [search_space]
diff --git a/tree b/tree
@@ -22,6 +22,7 @@
 - [tree_balanced]
 - [path]
 - [downward_path]
+- [tree_labeled]
 
 ## [Algorithms] on [trees]
 
@@ -71,6 +72,6 @@
 
 Up: [data_structure]
 
-See also: [treewidth], [forest]
+See also: [treewidth], [forest], [top_down], [bottom_up]
 
 Aliases: trees
diff --git a/tree_labeled b/tree_labeled
@@ -0,0 +1,9 @@
+# Tree labeled
+
+A [tree] where each [node] carries a [label] from a finite [alphabet]
+
+Notion used in [tree_languages]
+
+Up: [tree]
+
+Aliases: labeled tree
diff --git a/tree_language b/tree_language
@@ -2,6 +2,6 @@
 
 - [regular_tree_language]
 
-Up: [formal_language] of [tree]
+Up: [formal_language] of [labeled_tree]
 
 Aliases: tree languages
diff --git a/word b/word
@@ -1,6 +1,6 @@
 # Word
 
-Finite [sequence] of [letter]
+Finite [sequence] of [letters]
 
 - [primitive_word]
 - [twin]