commit 15e0b870b5a63eb4bba68fdfc5785bcd5a2cfb6c
parent 9f595124e4a353cecc58d580f79b9d9c519c1dcf
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 19 Jun 2025 00:27:22 +0200
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
22 files changed, 105 insertions(+), 17 deletions(-)
diff --git a/average b/average
@@ -0,0 +1,7 @@
+# Average
+
+relevant [academic_paper]: [hemenway1982classes]
+
+Up: [statistics]
+
+See also: [expectation]
diff --git a/computational_problem b/computational_problem
@@ -13,6 +13,7 @@
- [input]
- [output]
+- [instance]
- [complexity]
## Subareas
diff --git a/context_free_grammar_unambiguous b/context_free_grammar_unambiguous
@@ -1,11 +1,11 @@
# Unambiguous CFG
-An unambiguous CFG is a [context_free_grammar] where for every [word] in the language there is exactly one [derivation_tree]
+An *unambiguous CFG* is a [context_free_grammar] where for every [word] in the [formal_language] there is exactly one [derivation_tree]
[parsing] for an unambiguous CFG is more efficient
Up: [unambiguity], [context_free_grammar]
-See also: [inherently_ambiguous]
+See also: [inherently_ambiguous], [context_free_grammar_k_ambiguous]
Aliases: unambiguous CFG, unambiguous CFGs, CFG unambiguous, uCFG, uCFGs
diff --git a/core b/core
@@ -19,3 +19,5 @@ The [core] of an [instance] A is a [subinstance] B of A such that there is no [h
Up: [homomorphism]
See also: [chase_core]
+
+Aliases: cores
diff --git a/database_instance b/database_instance
@@ -8,4 +8,4 @@ Up: [database_theory]
Aliases: database, database instances
-See also: [instance]
+See also: [instance], [subdatabase]
diff --git a/degree_of_ambiguity b/degree_of_ambiguity
@@ -10,4 +10,4 @@
Up: [nondeterministic]
-See also: [density_function], [k_ambiguous_ddnnf]
+See also: [density_function], [k_ambiguous_ddnnf], [k_unambiguous]
diff --git a/disjunctive_normal_form_orthogonal b/disjunctive_normal_form_orthogonal
@@ -9,6 +9,8 @@ note that necessarily the clauses (all except at most one) must be big (at least
[disjunctive_normal_form_orthogonal_negation]
+Generalization: [k_unambiguous_DNF]
+
Up: [disjunctive_normal_form]
Aliases: unambiguous DNF, unambiguous DNFs, orthogonal DNF, orthogonal DNFs
diff --git a/expansion b/expansion
@@ -0,0 +1,7 @@
+# Expansion
+
+Given a [database_instance] I on a [relational_signature] σ, for a [supersignature] σ' of σ, the *reduct* of I on σ' is the [database_instance] J such that I is the [reduct] of J on σ
+
+See also: [reduct]
+
+Up: [database_instance]
diff --git a/friendship_paradox b/friendship_paradox
@@ -0,0 +1,7 @@
+# Friendship paradox
+
+https://en.wikipedia.org/wiki/Friendship_paradox
+
+Your friends have more friends than you do, on [average]
+
+Up: [paradox]
diff --git a/graph_perfect b/graph_perfect
@@ -6,4 +6,4 @@
Up: [graph_family]
-Aliases: perfect graph
+Aliases: perfect graph, perfect graphs
diff --git a/k_turn_pushdown_automata b/k_turn_pushdown_automata
@@ -0,0 +1,10 @@
+# K turn pushdown automata
+
+limits the alternation between [push_operation] and [pop_operation]
+
+- introduced in [ginsburg1966finite]
+- mentioned in [ganardi2018sliding]
+
+Up: [pushdown_automaton]
+
+See also: [visibly_pushdown_languages]
diff --git a/k_unambiguous_dnf b/k_unambiguous_dnf
@@ -0,0 +1,9 @@
+# K unambiguous DNF
+
+A [DNF] where for every [Boolean_valuation] there are at most k [clauses] that evaluate to true
+
+Special cases:
+- k=1: [disjunctive_normal_form_orthogonal]
+- k=2: [2_unambiguous_DNF]
+
+Up: [DNF], [k_unambiguous]
diff --git a/maximum_cut b/maximum_cut
@@ -2,10 +2,12 @@
https://en.wikipedia.org/wiki/Maximum_cut
-[np_complete]
+[NP_complete] according to [Garey_Johnson]
-[ptime] on [planar_graph] in connection with [chinese_postman_problem]
+[PTIME] on [planar_graphs] in connection with the [chinese_postman_problem]
See also: [minimum_cut]
Up: [computational_problem] on [graph]
+
+Aliases: maxcut, max cut
diff --git a/min_cost_hom b/min_cost_hom
@@ -0,0 +1,5 @@
+# Min cost hom
+
+cf [uppman2014computational]
+
+Up: [vcsp], [optimization_problem] on [homomorphism]
diff --git a/pushdown_automaton b/pushdown_automaton
@@ -4,14 +4,14 @@
[determinism]: [pushdown_automaton_deterministic]
-- k-turn pushdown automata: limits the alternation between [push_operation] and [pop_operation]
- - introduced in [ginsburg1966finite]
- - mentioned in [ganardi2018sliding]
+Restricted cases:
+- [k_turn_pushdown_automata]: limits the alternation between [push_operation] and [pop_operation]
+[Computational_problems]:
- [universality_automata_pushdown]
Up: [stack_automata]
-See also: [visibly_pushdown_automaton]
+See also: [visibly_pushdown_automaton], [pushdown_automaton_two_way]
-Aliases: pushdown automata
+Aliases: pushdown automata, PDA, PDAs
diff --git a/pushdown_automaton_two_way b/pushdown_automaton_two_way
@@ -0,0 +1,8 @@
+# Pushdown automaton two way
+
+- [2NPDA] ([nondeterministic_automata])
+- [2DPDA] ([deterministic_automata])
+
+Up: [pushdown_automaton], [automata_two_way]
+
+Aliases: 2PDA, 2PDAs, two way PDA, two way PDAs
diff --git a/subdatabase b/subdatabase
@@ -0,0 +1,12 @@
+# Subdatabase
+
+A [database_instance] which contains a subset of the facts of another [database_instance]
+
+Special case:
+- [reduct]
+
+Up: [database_instance]
+
+See also: [subgraph]
+
+Aliases: subinstance, subinstances, subdatabases
diff --git a/subgraph b/subgraph
@@ -6,4 +6,4 @@ Up: [graph]
Aliases: subgraphs
-See also: [subinstance]
+See also: [subinstance], [subdatabase], [induced_subgraph]
diff --git a/submodular_function b/submodular_function
@@ -6,4 +6,4 @@
[zivny2009expressive]: [submodular_function_locally_defined], i.e., a [sum] of [functions] of bounded [arity]
- related to [pseudo_boolean_optimization]
-Up: [function]
+Up: [function], [submodularity]
diff --git a/two_way_nondeterministic_pushdown_automaton b/two_way_nondeterministic_pushdown_automaton
@@ -4,6 +4,6 @@ mentioned in [bringmann2024nfa]
- [computational_problem]: [2NPDA_acceptance]
-Up: [automata_two_way], [pushdown_automaton]
+Up: [automata_nondeterministic], [2PDA]
-Aliases: 2NPDA
+Aliases: 2NPDA, 2NPDAs
diff --git a/unambiguous b/unambiguous
@@ -7,6 +7,6 @@
- [unambiguous_star_free_language]
- [word_automaton_unambiguous]
-See also: [unambiguity]
+See also: [unambiguity], [k_unambiguous]
Up: [formal_language_theory]
diff --git a/word_automaton_unambiguous b/word_automaton_unambiguous
@@ -0,0 +1,16 @@
+# Unambiguous word automata
+
+[inclusion], [equivalence] are in P [ptime] (even NC [nc]?) whereas they are [pspace] PSPACE-c for
+[word_automaton_nondeterministic]
+
+More restricted definition: [word_automaton_self_verifying]
+
+Variant: [word_automaton_exclusive]
+
+[unambiguous_word_automaton_complementation]
+
+Up: [word_automaton], [unambiguity]
+
+See also: [word_automaton_finitely_ambiguous], [word_automaton_polynomially_ambiguous], [word_automaton_k_unambiguous]
+
+Aliases: UFA, UFAs, unambiguous word automaton
