commit 2f011cec79e70259f4692a158b05542f096e9345
parent ab8693c6810aaf4670dfbba61d5e373a4c24b9e9
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 5 Feb 2025 16:00:07 +0100
commit with codex
Diffstat:
5 files changed, 6 insertions(+), 8 deletions(-)
diff --git a/context_free_grammar b/context_free_grammar
@@ -19,6 +19,7 @@
- [context_free_grammar_unambiguous]
- [context_free_grammar_linear]
- [context_free_grammar_bounded]
+- [context_free_grammar_polyslender]
- [context_free_grammar_finite]
- [inherently_ambiguous]
diff --git a/context_free_grammar_bounded b/context_free_grammar_bounded
@@ -1,6 +1,6 @@
# Bounded context-free grammar
-[polynomial] [density_function]
+[context_free_grammar] recognizing [language] which is [language_bounded]
Up: [context_free_grammar]
diff --git a/density_function b/density_function
@@ -5,6 +5,7 @@ function defined on an [automata] and giving the number of words of a given leng
possible regimes: exponential, polynomial, etc.
- [language_slender]
+- [language_polyslender]
- [language_polynomially_bounded]
[counting_problem] of evaluating it: [sharp_automaton]
diff --git a/lower_bounds b/lower_bounds
@@ -1,14 +1,9 @@
# Lower bounds
-Class at [mit] http://courses.csail.mit.edu/6.5440/fall23/
-
-videos and well-down course notes https://courses.csail.mit.edu/6.892/spring19/lectures/
-
-Work in progress [book] "Computational Intractability: A Guide to Algorithmic Lower Bounds" https://hardness.mit.edu/
-- not intended to be [open_access] apparently
+[complexity_lower_bounds]
Up: [computational_complexity]
-See also: [theorem]
+See also: [theorem], [upper_bound]
Aliases: lower bound
diff --git a/order b/order
@@ -5,5 +5,6 @@
- [inequality_mathematics]
- [linear_extension], see also [topological_sort]
- [well_quasi_ordering]
+- [upper_bound] / [lower_bound]
Up: [mathematics]
