commit d4502a8b9151d9735e52206e4037e934c0676a77
parent f23331941f5c67865ab23ca61cc05f80ba7c289c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 14 Sep 2025 09:28:50 +0200
commit with codex
Diffstat:
6 files changed, 25 insertions(+), 0 deletions(-)
diff --git a/circuit b/circuit
@@ -23,6 +23,7 @@
- [enumeration_circuit]
- [satisfiability]
+- [circuit_value_problem]
## Measure [circuit_parameter]
diff --git a/circuit_value_problem b/circuit_value_problem
@@ -0,0 +1,7 @@
+# Circuit value problem
+
+Given a [Boolean_circuit] with Boolean values on the gates, and a [gate], decide if that [gate] evaluates to [true]
+
+Up: [decision_problem] on [circuit]
+
+See also: [formula_value_problem]
diff --git a/context_free_grammar b/context_free_grammar
@@ -36,6 +36,7 @@
- [context_free_grammar_equivalence]
- [context_free_grammar_universality]
- [smallest_grammar_problem]
+- [context_free_grammar_membership]
## Fields
diff --git a/context_free_grammar_membership b/context_free_grammar_membership
@@ -0,0 +1,12 @@
+# Context free grammar membership
+
+Given a [CFG] G and a [word] w, decide whether w is accepted by G
+
+Can be studied in:
+- [combined_complexity]
+ - can do [CFG_parsing] like [CYK]
+- [data_complexity]: cf [context_free_language_membership]
+
+Up: [context_free_grammar], [membership_problem]
+
+See also: [context_free_language_membership]
diff --git a/context_free_language_membership b/context_free_language_membership
@@ -6,3 +6,5 @@
- [Valiant's_parser]
Up: [membership_problem], [context_free_language]
+
+See also: [context_free_grammar_membership]
diff --git a/tree_evaluation_problem b/tree_evaluation_problem
@@ -7,3 +7,5 @@ It is in O(log n log log n), cf [cook2023tree]
Up: [computational_problem] on [tree]
Aliases: TreeEval
+
+See also: [formula_value_problem]
