commit 8ea6551222f72614c328371149a8ec4be09238fb
parent bc354594d63a1f68bcf28ee56c1db4063c72b7a5
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 28 Apr 2026 17:54:10 +0200
commit with codex
Diffstat:
11 files changed, 48 insertions(+), 11 deletions(-)
diff --git a/cfg_multiplicity_equivalence b/cfg_multiplicity_equivalence
@@ -0,0 +1,13 @@
+# CFG multiplicity equivalence
+
+Two [CFGs] G1 and G2 are *multiplicity equivalent* if they recognize the same language with the same number of [parse_trees] for each [word]
+
+[Decision_problem]: [cfg_multiplicity_equivalence_problem]
+
+See [kuich2005multiplicity]
+
+Up: [CFG_equivalence]
+
+Aliases: multiplicity equivalent
+
+See also: [bag_semantics]
diff --git a/cfg_multiplicity_equivalence_problem b/cfg_multiplicity_equivalence_problem
@@ -0,0 +1,9 @@
+# CFG multiplicity equivalence problem
+
+The [equivalence_problem] on [CFGs] but for deciding [CFG_multiplicity_equivalence]
+
+It is an [open_problem] whether this is decidable
+
+See [kuich2005multiplicity]
+
+Up: [context_free_grammar_unambiguous_equivalence_problem]
diff --git a/context_free_grammar_unambiguous_equivalence_problem b/context_free_grammar_unambiguous_equivalence_problem
@@ -1,10 +1,12 @@
-# Context free grammar unambiguous equivalence problem
+# Unambiguous CFG equivalence problem
-It is an [open_problem] whether CFG equivalence is decidable when the input are two [uCFGs]. Same thing for the problem on arbitrary [CFGs] where we want equivalence in [bag_semantics] i.e., do the two [CFGs] recognize the same language with the same number of [parse_trees] for each [word]?
+It is an [open_problem] whether CFG equivalence is decidable when the input are two [uCFGs]. More general problem: [CFG_multiplicity_equivalence]
cf https://cstheory.stackexchange.com/questions/38598/is-equivalence-of-unambiguous-context-free-languages-decidable
-By contrast [language_inclusion] is [undecidable] because [DPDA_inclusion] is [undecidable]
+By contrast:
+- [language_inclusion] is [undecidable] because [DPDA_inclusion] is [undecidable]
+- equivalence of a [UCFG] with a [regular_language] is [decidable] according to [jez2013unambiguous] p2
Up: [context_free_grammar_equivalence_problem], [uCFGs]
diff --git a/dpda_inclusion b/dpda_inclusion
@@ -0,0 +1,10 @@
+# DPDA inclusion
+
+It is [undecidable], cf [ginsburg1965deterministic] Theorem 5.3 (b)
+or [asveld2000inclusion].
+
+See also: [context_free_grammar_unambiguous_equivalence_problem]
+
+Up: [language_inclusion_problem], [DPDA]
+
+Aliases: DPDA inclusion problem
diff --git a/equivalence_automata_pushdown_deterministic b/equivalence_automata_pushdown_deterministic
@@ -1,4 +1,4 @@
-# Equivalence automata pushdown deterministic
+# Deterministic Pushdown Automaton Equivalence
Was shown [decidable] by [senizergues1997equivalence]
@@ -8,6 +8,6 @@ Special case: [deterministic_k_turn_PDA_equivalence]
Up: [pushdown_automaton_deterministic], [automaton_equivalence]
-Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic, dpda equivalence, dpda equivalence problem
+Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic, dpda equivalence, dpda equivalence problem, Deterministic Pushdown Automaton Equivalence
See also: [context_free_grammar_unambiguous_equivalence_problem]
diff --git a/factor b/factor
@@ -1,6 +1,6 @@
# Factor
-Definition: [word] u is factor of [word] v if we have v = xuy for some [words] x and y
+Definition: a [word] u is a *factor* of [word] v if we have v = xuy for some [words] x and y
- [factor_universal]
- [factorial_language]
@@ -14,6 +14,6 @@ If u is a factor of v, then v is an [extension] of u
Up: [formal_language_theory]
-See also: [subword], [prefix], [suffix], [factor_avoidance]
+See also: [subword], [prefix], [suffix], [factor_avoidance], [extension]
Aliases: factors, infix, infixes
diff --git a/factor_closed_language b/factor_closed_language
@@ -6,4 +6,4 @@ Also closed "bifix-closed", because it is equivalent to being [prefix_closed] an
Up: [factor]
-See also: [factor_convex_language], [Prefix_closed_language], [Suffix_closed_language], [factor_free_language], [bifix_free_language], [bifix_convex_language]
+See also: [factor_convex_language], [Prefix_closed_language], [Suffix_closed_language], [factor_free_language], [bifix_free_language], [bifix_convex_language], [two_sided_ideal]
diff --git a/language_inclusion b/language_inclusion
@@ -1,4 +1,4 @@
-# Language inclusion
+# Language inclusion problem
- [pattern_language_inclusion]
- [language_inclusion_bounded]
@@ -7,3 +7,5 @@
- [CFG_language_inclusion]
Up: [formal_language_computational_problems], [set_inclusion]
+
+Aliases: language inclusion problem
diff --git a/partial_order b/partial_order
@@ -7,6 +7,7 @@ Variants:
- [poset_rank]
- [partial_order_dimension]
- connections to [treewidth]
+- [boolean_dimension]
- [crown] and link with [partial_order_dimension]
- [trotter1973dimension]
- [order_type]
diff --git a/poset_width b/poset_width
@@ -6,4 +6,4 @@ Can be computed in [PTIME] via [dilworths_theorem] using a [flow_algorithm]
Up: [partial_order]
-See also: [dilworths_theorem], [chain_partitioning], [partial_order_height]
+See also: [dilworths_theorem], [chain_partitioning], [partial_order_height], [poset_dimension]
diff --git a/right_extension b/right_extension
@@ -4,4 +4,4 @@ A [word] u is a *right extension* of a [word] v iff v is a [prefix] of u
Up: [prefix]
-See also: [distinguishing_extension]
+See also: [distinguishing_extension], [extension]
