commit 4ee01c05683efa74768cba14e0c9b9c3dcd88de1
parent c9dec37e0bd5a2672500f3978ae7ba702defc7ed
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 23 Dec 2025 13:01:27 +0100
commit with codex
Diffstat:
21 files changed, 169 insertions(+), 5 deletions(-)
diff --git a/cfl_commutative_closure_regular b/cfl_commutative_closure_regular
@@ -0,0 +1,8 @@
+# CFL commutative closure regular
+
+The [CFLs] whose [commutative_closure] is [regular_language]
+- cf https://cstheory.stackexchange.com/a/48457
+
+See also: [parikhs_theorem], [commutative_closure_does_not_preserve_regularity], [commutatively_regular]
+
+Up: [CFL]
diff --git a/commutatively_equivalent b/commutatively_equivalent
@@ -0,0 +1,5 @@
+# Commutatively equivalent
+
+In [carpi2021commutative]: two languages are *commutatively equivalent* if there is a [bijection] between them which preserves the [parikh_image]
+
+Up: [commutatively_regular]
diff --git a/commutatively_regular b/commutatively_regular
@@ -0,0 +1,9 @@
+# Commutatively regular
+
+In [carpi2021commutative]: a [formal_language] is *commutatively regular* if it is [commutatively_equivalent] to a [regular_language]
+
+Not straightforward to understand already for [CFLs], cf [carpi2021commutative]
+
+See also: [cfl_commutative_closure_regular]
+
+Up: [formal_language]
diff --git a/context_free_grammar b/context_free_grammar
@@ -9,6 +9,7 @@
- [derivation_tree]
- [context_free_language]
- [proto_word]
+- [derivation]
## Equivalence
@@ -20,8 +21,11 @@
- [context_free_grammar_deterministic]
- [context_free_grammar_unambiguous]
- [context_free_grammar_ambiguous]
-- [context_free_grammar_ultralinear]
- - [context_free_grammar_linear]
+- [context_free_grammar_linear]
+ - [context_free_grammar_ultralinear]
+ - [context_free_grammar_metalinear]
+ - [context_free_grammar_superlinear]
+ - [context_free_grammar_finite_index]
- [context_free_grammar_bounded]
- [context_free_grammar_polyslender]
- [context_free_grammar_finite]
diff --git a/context_free_grammar_finite_index b/context_free_grammar_finite_index
@@ -0,0 +1,24 @@
+# Finite index CFG
+
+Defined in [salomaa1973formal] Chapter VI section 10: A [CFG] G having a bound k such that every word in the [language_accepted_by] G has a [derivation] with [derivation_index] at most k
+
+Equivalent characterization:
+- non-expansive CFGs*, i.e., those where you cannot rewrite a nonterminal into
+ multiple copies of itself
+- closing the CFLs under substitution, where closing a family under
+ substitution means closing under the operation where you replace each letter
+ by a language of the family (cf [salomaa1973formal]): these are called the
+ "quasi-rational languages" ([autebert1997context], [shemetova2024rational])
+
+Strictly generalizes:
+- [ultralinear_CFGs]
+- [superlinear_CFGs]
+
+Variant:
+- [derivation_bounded_set], i.e., for a [CFG], the sublanguage of [derivation_trees] of bounded [derivation_tree_index]
+ - defined in [ginsburg1968derivation]
+ - also discussed in [esparza2016brief] in connection with [Strahler_number]
+
+Up: [context_free_grammar]
+
+Aliases: finite index CFG, finite index CFGs, quasirational, quasirational language, non-expansive CFG, non expansive CFG
diff --git a/context_free_grammar_metalinear b/context_free_grammar_metalinear
@@ -0,0 +1,7 @@
+# Context free grammar metalinear
+
+Defined in [salomaa1973formal]: a [CFG] is *metalinear* if its axiom rewrites in at most k [nonterminals] that are themselves linear
+
+Up: [context_free_grammar]
+
+Aliases: metalinear CFG, metalinear CFGs
diff --git a/context_free_grammar_superlinear b/context_free_grammar_superlinear
@@ -0,0 +1,16 @@
+# Superlinear CFG
+
+A CFG where the only allowed nonlinear derivations are of the form X -> YZ
+where Z is a linear nonterminal
+
+Cf [kutrib2007finite]
+
+Special case:
+- [metalinear_CFGs]
+
+Generalization:
+- [finite_index_CFGs]
+
+Up: [context_free_grammar]
+
+Aliases: superlinear CFG, superlinear CFGs
diff --git a/context_free_grammar_ultralinear b/context_free_grammar_ultralinear
@@ -1,9 +1,18 @@
-# Context free grammar ultralinear
+# Ultralinear CFG
-A [CFG] where there is a bound on the maximal number of [nonterminals] that can occur in any [derivation]
+A [CFG] where there is a bound on the maximal number of [nonterminals] that can occur in any [derivation], i.e., where the [derivation_index] of all [derivations] is bounded
Can be seen in terms of [PDAs] via the notion of [PDA_finite_turn], studied in [ginsburg1966finite]
-Special case: [linear_CFGs]
+Special cases:
+- [linear_CFGs]
+- [metalinear_CFGs]
+
+Generalization:
+- [finite_index_CFGs]
Up: [context_free_grammar]
+
+See also: [context_free_grammar_finite_index], [context_free_grammar_metalinear]
+
+Aliases: ultralinear CFG, ultralinear CFGs
diff --git a/derivation b/derivation
@@ -0,0 +1,13 @@
+# Derivation
+
+A *derivation* for a [CFG] G is a sequence of [protowords] starting at the [axiom] and where at every step some [nonterminal] is replaced by the [RHS] of a [production] for that [nonterminal]. If the derivation ends in a [word] w without [nonterminals], then it witnesses that w is in the [language_accepted_by] G
+
+Notion of [left_derivation], which is in bijection with [derivation_trees]
+
+- [derivation_index]
+
+Up: [context_free_grammar]
+
+See also: [derivation_tree]
+
+Aliases: derivations
diff --git a/derivation_index b/derivation_index
@@ -0,0 +1,11 @@
+# Derivation index
+
+The *index* of a [derivation] is the maximal number of [nonterminals] occurring in the [protowords] of the [derivation]
+
+Mentioned in [esparza2016brief], attributed to [ginsburg1968derivation]
+
+If you bound it on [CFGs] on all derivations, you get [ultralinear_CFGs]
+
+If you bound it by requiring that every accepted word has a derivation of bounded index, you get [finite_index_CFGs]
+
+Up: [derivation]
diff --git a/derivation_tree b/derivation_tree
@@ -6,6 +6,8 @@ The [yield] of a derivation tree is the sequence of its [leaves]
The notion of derivation trees also occurs in [datalog]: [derivation_tree_datalog]
+- [derivation_tree_index]
+
Up: [tree] for [context_free_grammar]
Aliases: parse tree, derivation trees, parse trees
diff --git a/derivation_tree_index b/derivation_tree_index
@@ -0,0 +1,9 @@
+# Derivation tree index
+
+The *index* of a [derivation_tree] is the minimal index of its [derivations] (defined in [esparza2016brief] Section 3.2)
+
+It is connected to its [Strahler_number] if the grammar is in [Chomsky_normal_form]
+
+Up: [derivation_tree]
+
+See also: [chytil1990caterpillars]
diff --git a/graph_problem b/graph_problem
@@ -26,6 +26,7 @@
- [graph_sandwich_problem]
- [planarity_testing]
- [recognition_problem]
+- [graph_realization_problem]
Up: [computational_problem] on [graph]
diff --git a/graph_realization_problem b/graph_realization_problem
@@ -0,0 +1,14 @@
+# Graph realization problem
+
+https://en.wikipedia.org/wiki/Graph_realization_problem
+
+[computational_problem] on [undirected_graphs]
+
+Can be solved in [PTIME]
+
+- [graph_realization_problem_digraph]
+- [graph_realization_problem_bipartite]
+
+Up: [graph_problem]
+
+See also: [degree]
diff --git a/graph_realization_problem_bipartite b/graph_realization_problem_bipartite
@@ -0,0 +1,9 @@
+# Graph realization problem bipartite
+
+https://en.wikipedia.org/wiki/Bipartite_realization_problem
+
+in [PTIME] but the partition into the two sides is given (= as two degree sequences)
+
+if the partition is not given (= given a degree sequence, is there a [bipartite_graph] that achieves it), the complexity is [open_problem], cf [miklos2025complexity]
+
+Up: [graph_realization_problem], [bipartite_graph]
diff --git a/graph_realization_problem_digraph b/graph_realization_problem_digraph
@@ -0,0 +1,7 @@
+# Graph realization problem digraph
+
+https://en.wikipedia.org/wiki/Digraph_realization_problem
+
+in [PTIME]
+
+Up: [graph_realization_problem], [directed_graph]
diff --git a/parikhs_theorem b/parikhs_theorem
@@ -7,3 +7,5 @@ https://en.m.wikipedia.org/wiki/Parikh's_theorem
The [Parikh_image] of a [CFL] is a [union] of finitely many [linear_sets], where a [linear_set] is an expression of the form u + M alpha over alpha the vectors with integer values, for u an origin vector and M a [matrix]
Up: [theorem] about [parikh_image]
+
+See also: [CFL_commutative_closure_regular]
diff --git a/production b/production
@@ -8,3 +8,5 @@ A pair of [proto_words]: expresses that the [LHS] can be rewritten to the [RHS]
Up: [formal_grammar]
Aliases: productions
+
+See also: [derivation]
diff --git a/proto_word b/proto_word
@@ -3,3 +3,5 @@
A *proto word* is a [word] on the extended [alphabet] consisting of [terminals] and [nonterminals]
Up: [context_free_grammar]
+
+Aliases: proto words, protoword, protowords
diff --git a/strahler_number b/strahler_number
@@ -4,6 +4,11 @@ https://en.wikipedia.org/wiki/Strahler_number
cf [esparza2016brief]
+- [strahler_number_formal_language]
+
+Related to [pathwidth] by a factor of 2
+- cf https://en.wikipedia.org/wiki/Strahler_number#Pathwidth
+
Up: [parameter] on [tree]
See also: [cantor_bendixson_rank]
diff --git a/strahler_number_formal_language b/strahler_number_formal_language
@@ -0,0 +1,5 @@
+# Strahler number formal language
+
+[derivation_tree_index]
+
+Up: [strahler_number], [formal_language_theory]
