commit 4b979b893349ac352a545b466b3d784a889fa23e
parent ea22af887fb004d8325be11810aad6e125f38ec5
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 20 Aug 2025 19:44:50 +0200
commit with codex
Diffstat:
16 files changed, 58 insertions(+), 18 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_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, 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_unambiguous b/universality_context_free_grammar_unambiguous
@@ -1,6 +1,8 @@
# 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]
