commit 7c28387bf75853ec9178c91ac7bef758f319616a
parent 18bf865942017835a09a6a99aca8eefde69a2b44
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 25 Jun 2025 09:22:08 +0200
commit with codex
Diffstat:
15 files changed, 93 insertions(+), 5 deletions(-)
diff --git a/2_ambiguous_cfg b/2_ambiguous_cfg
@@ -0,0 +1,7 @@
+# 2 ambiguous CFG
+
+An [ambiguous_CFG] where every [word] has at most two [parse_trees]
+
+Up: [degree_of_ambiguity_cfg]
+
+Aliases: 2 ambiguous CFGs
diff --git a/context_free_grammar b/context_free_grammar
@@ -11,12 +11,14 @@
## Equivalence
-[context_free_grammar_pushdown_automaton_equivalence]
+- [context_free_grammar_pushdown_automaton_equivalence]
+- [context_free_grammar_equivalence]
## Subclasses
- [context_free_grammar_deterministic]
- [context_free_grammar_unambiguous]
+ - [context_free_grammar_ambiguous]
- [context_free_grammar_linear]
- [context_free_grammar_bounded]
- [context_free_grammar_polyslender]
diff --git a/context_free_grammar_ambiguous b/context_free_grammar_ambiguous
@@ -0,0 +1,9 @@
+# Context free grammar ambiguous
+
+A [CFG] which is not an [unambiguous_CFG]: some [words] have multiple [parse_trees]
+
+Some ambiguous CFGs can be replaced by an [unambiguous_CFG] which is [CFG_equivalent], but others cannot because they recognize an [inherently_ambiguous_CFL]
+
+Up: [context_free_grammar], [ambiguity]
+
+Aliases: CFG ambiguous, ambiguous CFG, ambiguous CFGs
diff --git a/context_free_grammar_equivalence b/context_free_grammar_equivalence
@@ -0,0 +1,9 @@
+# Context free grammar equivalence
+
+Two [CFGs] are *equivalent* if they recognize the same [formal_language]
+
+- [computational_problem]: [context_free_grammar_equivalence_problem]
+
+Up: [context_free_grammar], [language_equivalence]
+
+Aliases: CFG equivalence, CFG equivalent
diff --git a/context_free_grammar_equivalence_problem b/context_free_grammar_equivalence_problem
@@ -0,0 +1,9 @@
+# Context free grammar equivalence problem
+
+The *context free grammar equivalence problem* is the [decision_problem] of testing, given two [CFGs], whether they are [CFG_equivalent]
+
+It is [undecidable] on [CFGs], by reduction from [CFG_universality]
+
+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]?
+
+Up: [formal_language_computational_problem], [context_free_grammar_equivalence]
diff --git a/context_free_grammar_unambiguous b/context_free_grammar_unambiguous
@@ -6,6 +6,6 @@ An *unambiguous CFG* is a [context_free_grammar] where for every [word] in the [
Up: [unambiguity], [context_free_grammar]
-See also: [inherently_ambiguous], [context_free_grammar_k_ambiguous]
+See also: [inherently_ambiguous], [context_free_grammar_k_ambiguous], [CFG_ambiguous]
Aliases: unambiguous CFG, unambiguous CFGs, CFG unambiguous, uCFG, uCFGs
diff --git a/degree_of_ambiguity b/degree_of_ambiguity
@@ -1,13 +1,16 @@
# Degree of ambiguity
-[asymptotic] number of [accepting_runs] of a [nondeterministic_automaton]
+[asymptotic] number of [accepting_runs] of a [nondeterministic_automaton] or [CFG]
+On language formalisms:
- [degree_of_ambiguity_nfa]
- [degree_of_ambiguity_tree_automata]
- [degree_of_ambiguity_cfg]
+By regime:
+- [k_unambiguous]
- [polynomial_ambiguity]
Up: [nondeterministic]
-See also: [density_function], [k_ambiguous_ddnnf], [k_unambiguous]
+See also: [density_function], [k_ambiguous_ddnnf]
diff --git a/degree_of_ambiguity_cfg b/degree_of_ambiguity_cfg
@@ -0,0 +1,14 @@
+# Degree of ambiguity cfg
+
+- [2_ambiguous_CFG]
+- [k_ambiguous_CFG]
+- [infinitely_ambiguous_CFGs]
+ - can be made arbitrarily low nonconstant, cf [wich2005sublogarithmic]
+ - [polynomial_ambiguity]
+ - [naji1998grad], quoted in conclusion of [wich2000exponential], gives
+ [CFLs] of inherent ambiguity of arbitrary [polynomial] degree, as well as
+ exponential
+
+Up: [degree_of_ambiguity], [CFG]
+
+See also: [inherently_ambiguous]
diff --git a/k_ambiguous b/k_ambiguous
@@ -1,6 +1,7 @@
# K ambiguous
-like [unambiguity] for [NFA] but every word has at most k accepting runs
+- [k_ambiguous_NFA]
+- [k_ambiguous_CFG]
Up: [unambiguity]
diff --git a/k_ambiguous_cfg b/k_ambiguous_cfg
@@ -0,0 +1,11 @@
+# K ambiguous CFG
+
+A *k ambiguous CFG* is a [CFG] where every [word] has at most k [parse_trees]
+
+Special cases:
+- k=1: [uCFGs]
+- k=2: [2_ambiguous_CFGs]
+
+Up: [k_ambiguous], [CFG]
+
+See also: [infinitely_ambiguous_CFG], [Degree_of_ambiguity_cfg]
diff --git a/k_ambiguous_nfa b/k_ambiguous_nfa
@@ -0,0 +1,7 @@
+# K ambiguous NFA
+
+A *k-unambiguous NFA* is an [NFA] where every [word] has at most k [accepting_runs]
+
+For k=1, we get the notion of [UFAs]
+
+Up: [k_ambiguous], [NFA]
diff --git a/pqe_ucq b/pqe_ucq
@@ -6,6 +6,8 @@
The complexity in the [query] of the [meta_dichotomy] criterion is open
- cf [amarilli2020dichotomy] which says so explicitly
+[RST_query]
+
Up: [pqe] for [union_of_conjunctive_queries]
See also: [pqe_unsafe]
diff --git a/push_pop b/push_pop
@@ -3,7 +3,10 @@
The kinds of [updates_word] where you can do [push_operations] and [pop_operations]
- [dynamic_membership_push_pop]
+- [push_pop_distance]
For [dynamic_membership]
Up: [update_word]
+
+Aliases: push pop edits
diff --git a/rst_query b/rst_query
@@ -0,0 +1,9 @@
+# RST query
+
+The prototypical [SJFCQ] for which [PQE] is [sharpP_hard]:
+
+ exists x y R(x), S(x, y), T(y)
+
+Up: [pqe_ucq]
+
+See also: [Hk_queries]
diff --git a/universality_context_free_grammar b/universality_context_free_grammar
@@ -5,3 +5,5 @@
Up: [universality_problem]
See also: [universality_automata]
+
+Aliases: CFG universality, context free grammar universality
