commit 3cd2d3b85c3e5f08c06ced4da1a85de78f7faf4e
parent 16fc9000b8b8ce723e443b6012e20fa49e9d5906
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 30 Jul 2025 00:30:44 +0200
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
14 files changed, 42 insertions(+), 16 deletions(-)
diff --git a/3_dimensional_matching_numerical b/3_dimensional_matching_numerical
@@ -2,10 +2,10 @@
https://en.wikipedia.org/wiki/Numerical_3-dimensional_matching
-NUMERICAL 3-DIMENSIONAL MATCHING: vertices are integers and the eges are all
-triples that sum to the same value S/n where S is the sum of all the X Y Z
+NUMERICAL 3-DIMENSIONAL MATCHING: [vertices] are integers and the [edges] are
+all triples that sum to the same value S/n where S is the sum of all the X Y Z
-[np_complete] by reduction from 3-PARTITION [3_partition] following
+[np_complete] by reduction from [3-PARTITION] following
http://courses.csail.mit.edu/6.892/spring19/scribe/lec2.pdf simply by adding
large values
diff --git a/3_partition b/3_partition
@@ -9,3 +9,5 @@ Hardness proof: [garey_johnson] page 96
Up: [decision_problem]
See also: [partition_problem], [4_partition], [3_dimensional_matching_numerical]
+
+Aliases: 3PARTITION
diff --git a/compression_algorithm b/compression_algorithm
@@ -9,4 +9,6 @@
- [huffman_algorithm]
- [run_length_encoding]
-Up: [computer_science]
+Up: [algorithm], [compression]
+
+Aliases: compression algorithms
diff --git a/context_free_grammar b/context_free_grammar
@@ -2,12 +2,13 @@
## Concepts
-- [nonterminal]
-- [terminal]
+- [nonterminals]
+- [terminals]
- [production]
- [axiom]
- [derivation_tree]
- [context_free_language]
+- [proto_word]
## Equivalence
diff --git a/context_free_grammar_equivalence b/context_free_grammar_equivalence
@@ -6,4 +6,4 @@ Two [CFGs] are *equivalent* if they recognize the same [formal_language]
Up: [context_free_grammar], [language_equivalence]
-Aliases: CFG equivalence, CFG equivalent
+Aliases: CFG equivalence, CFG equivalent, equivalent CFG, grammar equivalent
diff --git a/context_free_grammar_finite b/context_free_grammar_finite
@@ -2,10 +2,10 @@
A *finite CFG* is a [context_free_grammar] which represents a [finite_language]
-Unlike general [CFGs], for finite CFGs, there always exists a [grammar_equivalent] [unambiguous_CFG]
+Unlike general [CFGs], for finite CFGs, there always exists a [grammar_equivalent] [unambiguous_finite_CFG], but doubly exponential blowup ([mengel2025lower])
Up: [context_free_grammar], [language_finite]
See also: [slp], [factorized_database]
-Aliases: finite context free grammar
+Aliases: finite context free grammar, finite context free grammars, finite CFG, finite CFGs
diff --git a/dsdnnf b/dsdnnf
@@ -6,4 +6,4 @@ not closed under [complementation], cf [vinallsmeeth2024structured] by [harry]
Up: [knowledge_compilation_classes], [ddnnf], [sdnnf]
-Aliases: dSDNNFs
+Aliases: dSDNNFs, d_SDNNFs, d_SDNNF
diff --git a/first_order_model_checking b/first_order_model_checking
@@ -9,14 +9,15 @@
[first_order_property_conjecture] on the hardness of FO model checking, cf [gao2018completeness]
- it is a weaker version of [strong_exponential_time_hypothesis]
-## Bounded variables
+## On specific [logical_fragments]
- [first_order_model_checking_fok]
- [first_order_model_checking_fo2]
-## [parameterized_complexity]
+## [Computational_complexity]
-[fo_model_checking_parameterized_complexity]
+[FO_model_checking_complexity]
+- [fo_model_checking_parameterized_complexity]
Up: [model_checking] for [first_order_logic]
diff --git a/language_equivalence b/language_equivalence
@@ -10,6 +10,6 @@ test if two languages are the same
Up: [formal_language_computational_problem], [equivalence]
-See also: [query_equivalence], [language_inclusion], [regular_expression_equivalence], [automaton_equivalence]
+See also: [query_equivalence], [language_inclusion], [regular_expression_equivalence], [automaton_equivalence], [CFG_equivalent]
Aliases: language equivalent, language equivalence problem
diff --git a/mengel2025lower b/mengel2025lower
@@ -0,0 +1,7 @@
+# mengel2025lower
+
+by [stefan_mengel] and [harry], at [PODS_2025]
+
+Up: [academic_paper]
+
+Aliases: mengel2024lower
diff --git a/obdd b/obdd
@@ -5,7 +5,8 @@ A [deterministic] [bdd] with a [variable_order]
- [uobdd]
- [nobdd]
-[synthesis]: we can take [conjunction] and [disjunction] of two OBDDs where the [variable_order] is the same
+We can tractably take the [conjunction] and [disjunction] of two OBDDs where the [variable_order] is the same
+- [OBDD_conjunction]
Up: [bdd]
diff --git a/parameterized_algorithm b/parameterized_algorithm
@@ -4,4 +4,4 @@ An [algorithm] with a [parameter] used in the [computational_complexity] analysi
Up: [parameterized_complexity], [algorithm]
-Aliases: algorithm_parameterized
+Aliases: algorithm_parameterized, parameterized algorithms
diff --git a/proto_word b/proto_word
@@ -0,0 +1,5 @@
+# Proto word
+
+A *proto word* is a [word] on the extended [alphabet] consisting of [terminals] and [nonterminals]
+
+Up: [context_free_grammar]
diff --git a/unambiguous_finite_cfg b/unambiguous_finite_cfg
@@ -0,0 +1,7 @@
+# Unambiguous finite CFG
+
+A [finite_CFG] which is an [unambiguous_CFG]
+
+Doubly exponential separation bounds in [mengel2025lower]
+
+Up: [context_free_grammar_finite], [unambiguous_CFG]
