commit b510c2253ebd05b7e1f364e06ebef5b46cb92577
parent 4e03a65b7e4da0ede663d419ab986ab3b4a92c10
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 11 Sep 2025 11:49:10 +0200
commit with codex
Diffstat:
18 files changed, 68 insertions(+), 12 deletions(-)
diff --git a/boolean_formula b/boolean_formula
@@ -14,4 +14,4 @@ Up: [representation] of [boolean_function]
See also: [boolean_circuit], [knowledge_compilation_classes]
-Aliases: formula boolean, Boolean formulae, Boolean formulas
+Aliases: formula boolean, Boolean formulae, Boolean formulas, propositional formula, propositional formulas
diff --git a/circuit_equivalence b/circuit_equivalence
@@ -2,4 +2,8 @@
The [computational_problem] of deciding, given two [Boolean_circuits], whether they represent the same [Boolean_function]
+- [circuit_equivalence_dDNNF]
+
Up: [Boolean_function_equivalence], [circuit]
+
+Aliases: circuit equivalence problem
diff --git a/compression b/compression
@@ -6,5 +6,6 @@
- [compression_string]
- [algorithms_on_compressed_data]
- [compression_natural_language]
+- [grammar_compression]
Up: [computer_science]
diff --git a/context_free_grammar_deterministic b/context_free_grammar_deterministic
@@ -6,4 +6,6 @@ no good intrinsic formulation in terms of [CFGs]
Up: [context_free_grammar], [determinism]
-Aliases: DCFG, DCFGs
+Aliases: DCFG, DCFGs, deterministic CFG, deterministic CFGs
+
+See also: [context_free_language_deterministic], [DPDA]
diff --git a/context_free_grammar_linear b/context_free_grammar_linear
@@ -7,3 +7,5 @@ Testing [language_emptiness] of [intersection] is already [undecidable] by reduc
Up: [context_free_grammar]
Aliases: linear grammar, linear grammars, linear context-free grammar, linear context-free grammars, linear CFG, linear CFGs
+
+See also: [context_free_language_linear]
diff --git a/context_free_grammar_unambiguous b/context_free_grammar_unambiguous
@@ -1,8 +1,13 @@
-# Unambiguous CFG
+# Unambiguous CFG (uCFG)
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
+[parsing] for an unambiguous CFG can be done in [quadratic_time]
+- https://cstheory.stackexchange.com/a/10504
+
+There are some [CFLs] admitting no uCFG (namely, those that are not [uCFLs]), and there is no computable function bounding the conciseness gap between uCFGs and [CFGs]: there are [uCFLs] where the smallest uCFG is arbitrarily larger than the smallest CFG.
+
+[Computational_problems]:
- [unambiguous_cfg_equivalence_problem]
- [unambiguous_cfg_universality]
diff --git a/context_free_language b/context_free_language
@@ -9,6 +9,9 @@
Subclass:
- [context_free_language_unambiguous]
+- [context_free_language_deterministic]
+- [context_free_language_linear]
+- [context_free_language_deterministic_linear]
Up: [language], [context_free_grammar]
diff --git a/context_free_language_deterministic b/context_free_language_deterministic
@@ -0,0 +1,11 @@
+# Context free language deterministic
+
+A [CFL] for which there is a [deterministic_CFG]
+
+Subclasses:
+
+- [context_free_language_deterministic_linear]
+
+Up: [context_free_language]
+
+Aliases: DCFL, DCFLs
diff --git a/counting_problem b/counting_problem
@@ -5,7 +5,8 @@
- in [graph]:
- [matching_counting]
- [triangle_counting]
- - [maximal_independent_set_counting] Counting [maximal_independent_set]
+ - [maximal_independent_set_counting]
+ - [subgraph_counting]
- [counting_query_answers]
- [counting_cqs]
- For [satisfiability_boolean]: [sharp_satisfiability]
diff --git a/ddnnf b/ddnnf
@@ -2,7 +2,7 @@
[deterministic] [decomposable] [nnf]
-testing [circuit_equivalence] of d-DNNFs is in [coRP]: [darwiche2002testing]
+[circuit_equivalence_problem]: [circuit_equivalence_dDNNFs]
Up: [knowledge_compilation_classes], [dd]
diff --git a/knowledge_compilation b/knowledge_compilation
@@ -12,3 +12,5 @@ Classes of [circuit] ensuring tractability
[circuit_bounds_vs_complexity_bounds]
Up: [theoretical_computer_science]
+
+Aliases: KC
diff --git a/language_finite b/language_finite
@@ -10,4 +10,4 @@ Up: [regular_language_family]
Aliases: finite language, finite languages
-See also: [automaton_finiteness]
+See also: [automaton_finiteness], [language_infinite]
diff --git a/maximal_independent_set b/maximal_independent_set
@@ -5,3 +5,5 @@
Up: [independent_set]
See also: [maximum_independent_set]
+
+Aliases: maximal independent sets
diff --git a/shuffle b/shuffle
@@ -3,6 +3,7 @@
A [word] w is a *shuffle* of two [words] u and v if we can interleave the characters of u and v to form w. We can also define the *shuffle* of two [formal_languages] L and L' as the set of [words] w that are shuffles of a [word] of L and a [word] of L'
- [shuffle_square]
+- [shuffle_membership]
- a finite set of [words] can be decomposed into at most one multiset of which it is the shuffle:
- see [berstel2002shuffle]
diff --git a/shuffle_membership b/shuffle_membership
@@ -0,0 +1,9 @@
+# Shuffle membership
+
+The [language_membership_problem] to a [formal_language] which is the [shuffle] of two [formal_languages]:
+
+- e.g., [berglund2012membership] shows [NP_hardness] of that problem for the [shuffle] of two [deterministic_linear_CFLs]
+
+Up: [shuffle]
+
+See also: [Constrained_topological_sort]
diff --git a/smallest_grammar_problem b/smallest_grammar_problem
@@ -1,10 +1,12 @@
# Smallest grammar problem
-The [computational_problem] of finding the smallest [CFG] that generates a specific set of [words].
+The [computational_problem] of finding the smallest [CFG], in various contexts:
-It is [np_complete]
-
-Studied in [charikar2005smallest]
+- for a single word, i.e., [grammar_compression]
+- for [finite_languages]: the smallest [CFG] that generates a specific set of [words]
+ - it is [np_complete]
+ - studied in [charikar2005smallest]
+- for for [infinite_languages], cf [bucher1981concise]
Up: [minimization] of [context_free_grammar]
diff --git a/subgraph_counting b/subgraph_counting
@@ -0,0 +1,11 @@
+# Subgraph counting
+
+For a class \calH of graph, the *subgraph counting problem* is the following: given a graph G and a pattern graph H in \calH, count how many [subgraphs] of G are [graph_isomorphic] to H
+
+Studied in [curticapean2014complexity]: on [recursively_enumerable] classes \calH, tractable if and only if \calH has bounded [vertex_cover_number]
+
+Up: [counting_problem]
+
+See also: [Graph_packing]
+
+Aliases: subgraph counting problem
diff --git a/vertex_cover b/vertex_cover
@@ -25,6 +25,6 @@ A vertex cover in a [graph] is a [subset] of [vertices] such that every [edge] i
- [koenigs_theorem]: on [bipartite_graphs] they have the same size
- The [complement] of a vertex cover is an [independent_set] so [minimum_vertex_cover] corresponds to [maximal_independent_set]
-See also: [edge_cover], [vertex_packing], [independent_set], [hitting_set], [set_cover]
+See also: [edge_cover], [vertex_packing], [independent_set], [hitting_set], [set_cover], [vertex_cover_number]
Up: [graph_substructure]
