commit 3bc316a100322fd29f975c74670890ffabc401e1
parent 626ae6ff9c758ea44fd0a772d9fd815263fc7687
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 18 Aug 2026 14:46:43 +0200
commit with codex
Diffstat:
23 files changed, 77 insertions(+), 24 deletions(-)
diff --git a/automata_complementation b/automata_complementation
@@ -1,8 +1,8 @@
# Automata complementation
-- in [linear_time] for [automata_deterministic]
-- exponential lower bound on [state_complexity] for [automata_nondeterministic]
-- hard also for [word_automaton_unambiguous]
+- [DFA_complementation]
+- [NFA_complementation]
+- [UFA_complementation]
Up: [automaton_constructions], [complementation]
diff --git a/automata_constructions b/automata_constructions
@@ -11,4 +11,6 @@
Up: [automata], [constructions]
-Aliases: automaton construction, automaton constructions
+Aliases: automaton construction, automaton constructions, automaton operation, automata operations
+
+See also: [CFG_constructions]
diff --git a/automaton_complete b/automaton_complete
@@ -8,6 +8,6 @@ We can do [automaton_completion] to transform an [incomplete_automata] into a co
Up: [automata_types]
-Aliases: complete automaton, complete automata, complete DFA, complete DFAs
+Aliases: complete automaton, complete automata, complete DFA, complete DFAs, DFA complete
See also: [automaton_trimmed]
diff --git a/automaton_intersection b/automaton_intersection
@@ -5,6 +5,6 @@ can be done with [product_construction]
- [DFA_intersection]
- [NFA_intersection]
-Up: [automaton_constructions], [intersection]
+Up: [automaton_constructions], [language_intersection]
-See also: [regular_expression_conjunction]
+See also: [regular_expression_conjunction], [CFG_intersection]
diff --git a/context_free_grammar b/context_free_grammar
@@ -39,13 +39,11 @@
## Problems
-- [context_free_grammar_equivalence]
-- [context_free_grammar_inclusion]
-- [context_free_grammar_universality]
-- [smallest_grammar_problem]
-- [context_free_grammar_membership]
-- [context_free_grammar_ambiguity_problem]
-- [context_free_grammar_enumeration]
+[context_free_grammar_problems]
+
+## Operations
+
+- [context_free_grammar_operation]
## Fields
diff --git a/context_free_grammar_ambiguity_problem b/context_free_grammar_ambiguity_problem
@@ -4,6 +4,6 @@ The [computational_problem] of [deciding] if a [CFG] is [uCFG]
Already [undecidable] for very restricted [linear_CFGs] by reduction from [PCP]
-Up: [ambiguity_problem], [context_free_grammar]
+Up: [ambiguity_problem], [context_free_grammar_problem]
See also: [context_free_language_inherent_ambiguity_problem]
diff --git a/context_free_grammar_enumeration b/context_free_grammar_enumeration
@@ -2,7 +2,7 @@
- [cfg_enumeration_blit]
-Up: [context_free_grammar], [enumeration]
+Up: [context_free_grammar_problem], [enumeration]
See also: [automaton_enumeration]
diff --git a/context_free_grammar_equivalence b/context_free_grammar_equivalence
@@ -6,7 +6,7 @@ Two [CFGs] are *equivalent* if they recognize the same [formal_language]
in [practice]: [context_free_grammar_equivalence_practice]
-Up: [context_free_grammar], [language_equivalence]
+Up: [context_free_grammar_problems], [language_equivalence]
Aliases: CFG equivalence, CFG equivalent, equivalent CFG, grammar equivalent
diff --git a/context_free_grammar_inclusion b/context_free_grammar_inclusion
@@ -2,7 +2,9 @@
It is [undecidable], already for [uCFLs], and already for [linear_uCFLs], see [asveld2000note]
-Up: [inclusion_problem], [context_free_grammar]
+However, it is [decidable] whether a [CFG] G is included in a given [NFA] A, because it amounts to the [negation] of [deciding] [CFG_emptiness] of the [CFG_automaton_intersection] of G and the [NFA_complement] of A
+
+Up: [inclusion_problem], [context_free_grammar_problem]
Aliases: CFG inclusion, CFG language inclusion
diff --git a/context_free_grammar_membership b/context_free_grammar_membership
@@ -9,6 +9,6 @@ Can be studied in:
- [context_free_grammar_membership_streaming]
-Up: [context_free_grammar], [membership_problem]
+Up: [context_free_grammar_problem], [membership_problem]
See also: [context_free_language_membership]
diff --git a/context_free_grammar_problems b/context_free_grammar_problems
@@ -0,0 +1,16 @@
+# Context free grammar problems
+
+- [context_free_grammar_equivalence]
+- [context_free_grammar_inclusion]
+- [context_free_grammar_universality]
+- [context_free_grammar_emptiness]
+- [context_free_grammar_membership]
+- [context_free_grammar_ambiguity_problem]
+ - [context_free_language_inherent_ambiguity_problem]
+- [context_free_grammar_enumeration]
+
+- [smallest_grammar_problem]
+
+Up: [computational_problem] on [context_free_grammar]
+
+Aliases: context free grammar problem, CFG problem, CFG problems
diff --git a/context_free_language b/context_free_language
@@ -1,6 +1,6 @@
# Context free language
-[language] accepted by [context_free_grammar]
+A [formal_language] accepted by a [context_free_grammar]
- [context_free_language_membership]
- [context_free_language_slender]
@@ -28,3 +28,5 @@ Variants:
Up: [language], [context_free_grammar]
Aliases: context-free languages, context free languages, context-free language, CFL, CFLs
+
+See also: [CFG_operation]
diff --git a/epsilon_production b/epsilon_production
@@ -0,0 +1,9 @@
+# Epsilon production
+
+An *epsilon production* of a [CFG] is a [production] of the form N → ε where ε denotes the [empty_word].
+
+Any CFG G can be rewritten to a CFG G' which does not have epsilon-productions and whose set of [derivation_trees] is in bijection with that of G
+
+Up: [context_free_grammar]
+
+See also: [epsilon_transition], [epsilon_transition_removal]
diff --git a/goldbach_conjecture b/goldbach_conjecture
@@ -1,6 +1,9 @@
# Goldbach conjecture
+https://en.wikipedia.org/wiki/Goldbach's_conjecture
+
- [ternary_goldbach_problem]
+- [vinogradov's_theorem]
See also: [twin_prime_conjecture], [chens_theorem]
diff --git a/graph_h_free b/graph_h_free
@@ -10,3 +10,5 @@ Each [undirected_graph] H thus defines a [graph_family]
Up: [graph_free]
See also: [induced_h_free], [h_minor_free]
+
+Aliases: H free graph, H free graphs, Hfree graph, Hfree graphs
diff --git a/graph_h_minor_free b/graph_h_minor_free
@@ -12,4 +12,4 @@ Up: [graph_free]
See also: [graph_h_free]
-Aliases: H minor free, minor free, H minor free graph, H minor free graphs, excluded minor, graph excluding minor, graphs excluding minor, graph excluding minors, H free graph, H free graphs
+Aliases: H minor free, minor free, H minor free graph, H minor free graphs, excluded minor, graph excluding minor, graphs excluding minor, graph excluding minors
diff --git a/language_emptiness b/language_emptiness
@@ -3,6 +3,7 @@
The [computational_problem] of deciding if a [formal_language] is [empty_language]
- [automaton_emptiness]
+- [CFG_emptiness]
Can be [undecidable] for some formalisms:
- cf https://cstheory.stackexchange.com/q/21741
diff --git a/language_intersection b/language_intersection
@@ -2,6 +2,12 @@
The [intersection] of two [formal_languages]
+- [automaton_intersection]
+ - [NFA_intersection]
+ - [DFA_intersection]
+
+- [CFG_intersection]
+
Up: [formal_language_operator], [intersection]
See also: [language_union]
diff --git a/semigroup_cancellative b/semigroup_cancellative
@@ -9,4 +9,4 @@ Up: [semigroup]
Aliases: cancellative semigroup, cancellative semigroups
-See also: [cancellation]
+See also: [cancellation], [weakly_cancellative]
diff --git a/semiring_absorptive b/semiring_absorptive
@@ -10,6 +10,6 @@ Generalization: [semiring_p_stable]
Up: [dioid]
-See also: [absorptivity]
+See also: [absorptivity], [weakly_absorptive]
Aliases: absorptive semiring, absorptive semirings
diff --git a/ternary_goldbach_problem b/ternary_goldbach_problem
@@ -2,6 +2,11 @@
https://en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture
+Weaker form: [Vinogradov's_theorem]
+
See also: [goldbach_conjecture]
Up: [number_theory]
+
+Aliases: Goldbach's_weak_conjecture
+
diff --git a/universality_context_free_grammar b/universality_context_free_grammar
@@ -5,7 +5,7 @@
- for [uCFGs]: [universality_context_free_grammar_unambiguous]
- for [linear_CFGs]: [linear_CFG_universality]
-Up: [universality_problem]
+Up: [universality_problem], [CFG_problem]
See also: [universality_automata], [CFG_language_inclusion], [CFG_equivalence]
diff --git a/vinogradovs_theorem b/vinogradovs_theorem
@@ -0,0 +1,7 @@
+# Vinogradov's theorem
+
+https://en.wikipedia.org/wiki/Vinogradov%27s_theorem
+
+any sufficiently large odd integer can be written as a sum of three [prime_numbers]
+
+Up: [goldbach_conjecture]
