commit 03238d6df2812ed25d92903a5fdd95bc772b4d7a
parent 645504ca309016406f99afa2d75f214cac83a500
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 21 Aug 2025 09:05:01 +0200
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
19 files changed, 64 insertions(+), 20 deletions(-)
diff --git a/automaton_inclusion b/automaton_inclusion
@@ -1,9 +1,9 @@
# Automaton inclusion
-[pspace_complete] for [automata_nondeterministic]
+[PSPACE_complete] for [nondeterministic_automata]
-[ptime] for [automata_deterministic]
+[PTIME] for [automata_deterministic]
-Up: [automata_problems], [set_inclusion]
+Up: [automata_problems], [language_inclusion]
-See also: [automaton_equivalence], [language_inclusion]
+See also: [automaton_equivalence]
diff --git a/bounded_language b/bounded_language
@@ -5,3 +5,5 @@ A [formal_language] L is *bounded* if there are words w_1, ..., w_k such that L
Up: [formal_language]
See also: [polyslender], [CFL]
+
+Aliases: language bounded, bounded languages
diff --git a/context_free_grammar b/context_free_grammar
@@ -34,6 +34,7 @@
## Problems
- [context_free_grammar_equivalence]
+- [context_free_grammar_universality]
- [smallest_grammar_problem]
## Fields
diff --git a/context_free_grammar_bounded b/context_free_grammar_bounded
@@ -1,7 +1,9 @@
# Bounded context-free grammar
-[context_free_grammar] recognizing [language] which is [language_bounded]
+A [context_free_grammar] that recognizes a [formal_language] which is [language_bounded]
Up: [context_free_grammar]
-See also: [regular_language_sparse]
+See also: [polyslender_CFL]
+
+Aliases: bounded CFG, bounded CFGs
diff --git a/context_free_grammar_polyslender b/context_free_grammar_polyslender
@@ -1,8 +1,6 @@
# Context free grammar polyslender
-[CFG] recognizing a [formal_language] which is [polyslender]
-
-[illie2000characterization]: a [context_free_language] is [polyslender] iff it is [bounded]
+[CFG] recognizing a [polyslender_CFL]
Up: [context_free_grammar], [polyslender]
diff --git a/context_free_grammar_unambiguous_equivalence_problem b/context_free_grammar_unambiguous_equivalence_problem
@@ -4,6 +4,8 @@ It is an [open_problem] whether CFG equivalence is decidable when the input are
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]
+
Up: [context_free_grammar_equivalence_problem], [uCFGs]
-Aliases: unambiguous CFG equivalence problem
+Aliases: unambiguous CFG equivalence problem, equivalence context free grammar unambiguous
diff --git a/context_free_language_polyslender b/context_free_language_polyslender
@@ -0,0 +1,9 @@
+# Context free language polyslender
+
+A [CFL] which is [polyslender]
+
+[illie2000characterization]: a [CFL] is [polyslender] iff it is [language_bounded]
+
+See also: [context_free_grammar_polyslender]
+
+Aliases: polyslender CFL, polyslender CFLs
diff --git a/deterministic_k_turn_pushdown_automata_equivalence b/deterministic_k_turn_pushdown_automata_equivalence
@@ -1,8 +1,8 @@
# Deterministic k turn pushdown automata equivalence
- the [equivalence_problem] is [decidable], cf [valiant1974decidability]
-- subsumed by [senizergues1997equivalence]
+- subsumed by [senizergues1997equivalence] which shows [decidability] of [DPDA_equivalence]
-Up: [equivalence_problem], [k_turn_pushdown_automata]
+Up: [language_equivalence_problem], [k_turn_pushdown_automata]
Aliases: deterministic k turn PDA equivalence
diff --git a/equivalence_automata_pushdown_deterministic b/equivalence_automata_pushdown_deterministic
@@ -4,6 +4,8 @@ Was shown [decidable] by [senizergues1997equivalence]
Is in [TOWER], cf [jancar2014equivalences]
+Special case: [deterministic_k_turn_PDA_equivalence]
+
Up: [pushdown_automaton_deterministic], [automaton_equivalence]
-Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic
+Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic, dpda equivalence, dpda equivalence problem
diff --git a/formal_language_operator b/formal_language_operator
@@ -20,3 +20,5 @@ An [operator] that takes one or two [formal_languages] and creates a new [formal
- [commutative_closure]
Up: [formal_language], [operator]
+
+Aliases: language operator, language operators
diff --git a/k_ambiguous_cfg b/k_ambiguous_cfg
@@ -1,11 +1,13 @@
# K ambiguous CFG
-A *k ambiguous CFG* is a [CFG] where every [word] has at most k [parse_trees]
+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]
+It is an [open_problem] whether every k-ambiguous CFG can be written as a [language_union] of k [uCFGs], but within [bounded_CFGs] this is known to be true, cf [wich2005ambiguity] p181 point (iv).
+
Up: [k_ambiguous], [CFG]
See also: [infinitely_ambiguous_CFG], [Degree_of_ambiguity_cfg]
diff --git a/language_equivalence b/language_equivalence
@@ -4,8 +4,10 @@ test if two languages are the same
- on [regular_languages]: [regular_language_equivalence]
- [pspace_complete]
-- on [context_free_languages]: [context_free_grammar_equivalence]
- - [undecidability]
+- on [context_free_languages]:
+ - [context_free_grammar_equivalence_problem]
+ - [undecidability]
+ - [DPDA_equivalence_problem]
- on [pattern_languages]: [pattern_language_equivalence]
Up: [formal_language_computational_problem], [equivalence]
diff --git a/language_inclusion b/language_inclusion
@@ -2,7 +2,7 @@
- [pattern_language_inclusion]
- [language_inclusion_bounded]
+- [DPDA_language_inclusion]
+- [automaton_inclusion]
Up: [formal_language_computational_problems], [set_inclusion]
-
-See also: [automaton_inclusion]
diff --git a/language_intersection b/language_intersection
@@ -0,0 +1,7 @@
+# Language intersection
+
+The [intersection] of two [formal_languages]
+
+Up: [formal_language_operator], [intersection]
+
+See also: [language_union]
diff --git a/language_polyslender b/language_polyslender
@@ -3,7 +3,10 @@
[Formal_language] whose [density_function] is [upper_bounded] by a [polynomial]
- [context_free_grammar_polyslender]
+- [regular_language_polyslender]
Up: [formal_language], [density_function]
See also: [language_slender], [bounded_language]
+
+Aliases: polyslender
diff --git a/language_union b/language_union
@@ -0,0 +1,7 @@
+# Language union
+
+The [union] of two [formal_languages]. It is one of the [language_operators] used to define [regular_expressions]
+
+Up: [union], [Formal_language_operator]
+
+See also: [language_intersection]
diff --git a/universality_context_free_grammar b/universality_context_free_grammar
@@ -8,4 +8,4 @@ Up: [universality_problem]
See also: [universality_automata]
-Aliases: CFG universality, context free grammar universality
+Aliases: CFG universality, context free grammar universality, universality CFG
diff --git a/universality_context_free_grammar_unambiguous b/universality_context_free_grammar_unambiguous
@@ -1,7 +1,11 @@
# Universality context free grammar unambiguous
-it is [decidable]: https://cstheory.stackexchange.com/a/41001
+it is [decidable] and in [PSPACE]:
+- https://cstheory.stackexchange.com/a/41001
+- [clemente2020complexity]
Up: [universality_context_free_grammar], [uCFGs]
Aliases: context free grammar unambiguous universality
+
+See also: [equivalence_context_free_grammar_unambiguous]
diff --git a/universality_problem b/universality_problem
@@ -3,6 +3,7 @@
[computational_problem], given a [formal_language], of deciding whether it is [language_universal]
- [universality_automata]
+- [universality_cfg]
Up: [computational_problem], [formal_language]
