wiki_research

commit 3ed32d94379637adf786c9c0bc0d309e3616cb34
parent 2165daa6e343ee6a4a47d1e582b6c761b659d4d3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue,  4 Feb 2025 00:23:41 +0100

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
automata_constructions
 | 
1
+
automata_nondeterministic
 | 
2
+-
context_free_grammar
 | 
4
++++
degree_of_ambiguity_tree
 | 
7
+++++++
derivation_tree
 | 
6
+++++-
equivalence_relation
 | 
7
+++++++
incidence_structure
 | 
13
+++++++++++++
learning_dfa
 | 
2
++
nondeterministic
 | 
4
++--
optimization
 | 
2
+-
query_evaluation
 | 
2
++
random_graph
 | 
4
+++-
randomness
 | 
1
+
tree
 | 
3
++-
tree_labeled
 | 
9
+++++++++
tree_language
 | 
2
+-
word
 | 
2
+-

17 files changed, 62 insertions(+), 9 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
@@ -36,6 +36,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/degree_of_ambiguity_tree b/degree_of_ambiguity_tree
@@ -0,0 +1,7 @@
+# Degree of ambiguity of a tree automaton
+
+[gallot2025structure]: it can be computed in [ptime]
+
+Up: [degree_of_ambiguity] of [tree_automaton]
+
+See also: [Density_function]
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/incidence_structure b/incidence_structure
@@ -0,0 +1,13 @@
+# Incidence structure
+
+https://en.wikipedia.org/wiki/Incidence_structure
+
+a relationship between two kinds of objects
+
+essentially a [graph_bipartite]
+
+[self_dual] if [isomorphism] when swapping both sides
+
+the corresponding graph is called the [levi_graph]
+
+Up: [mathematics]
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/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/query_evaluation b/query_evaluation
@@ -16,6 +16,8 @@
 
 - [query_evaluation_incremental]
 
+- [approximate_query_evaluation]
+
 Up: [database_theory]
 
 See also: [query_language], [enumeration_query_answers]
diff --git a/random_graph b/random_graph
@@ -4,4 +4,6 @@ also: [random_dfa]
 
 Up: [graph], [randomness]
 
-See also: [random_walk]
+See also: [random_walk], [random_hypergraph]
+
+Aliases: random graphs, graph random
diff --git a/randomness b/randomness
@@ -9,6 +9,7 @@
 ## [random_structure]
 
 - [random_graph]
+- [random_hypergraph]
 - [random_walk]
 - [random_dfa]
 
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]