commit b8ac383eeb801039197bed8c8f9f980116bebe2b
parent 9a464ad675f4a4d4437e87833f8f34633e7c6a1b
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 26 Feb 2025 11:17:55 +0100
commit with codex
Diffstat:
25 files changed, 134 insertions(+), 8 deletions(-)
diff --git a/automaton_epsilon_transitions b/automaton_epsilon_transitions
@@ -3,3 +3,5 @@
[automata_nondeterministic] with [epsilon_transition]
Up: [automata_types]
+
+Aliases: NFA epsilon
diff --git a/complexity_measure b/complexity_measure
@@ -0,0 +1,8 @@
+# Complexity measure
+
+- [complexity_time]
+- [complexity_space]
+- [incremental_time]
+- [enumeration_delay]
+
+Up: [computational_complexity]
diff --git a/complexity_space b/complexity_space
@@ -1,6 +1,8 @@
# Complexity_space
-- [savitchs_theorem]: we can simulate [nondeterministic] machine with quadratic blowup in space
+- [savitchs_theorem]: we can simulate [nondeterministic] machine with [quadratic] blowup in space
+
+- [catalytic_space]
Up: [complexity_measure]
diff --git a/computational_problem b/computational_problem
@@ -36,6 +36,7 @@
- [word_problem]
- [tiling_problem]
- [domino_problem]
+- [tree_evaluation_problem]
Up: [theoretical_computer_science]
diff --git a/cycle_rank b/cycle_rank
@@ -2,6 +2,16 @@
https://en.wikipedia.org/wiki/Cycle_rank
+The *cycle rank* of a [DAG] is 0
+
+The *cycle rank* of a [directed_graph] which is not [strongly_connected_graph] is the [maximum] of the cycle rank of the [SCCs]
+
+The *cycle rank* of a [strongly_connected_graph] is 1 plus the [minimum] across all [vertices] v of the cycle rank of the [graph] obtained by [vertex_deletion] of v
+
+It is a kind of analogue of [tree_depth] but for [directed_graphs] instead of [undirected_graphs]
+
+The [computational_problem] of computing cycle rank is [NP_hard]
+
See also: [feedback_edge_number], [pathwidth_directed], [treewidth_directed], [circuit_rank], [strahler_number], [star_height], [eggans_theorem], [cycle]
-Up: [width_measure] for [graph_directed]
+Up: [width_measure] for [directed_graph]
diff --git a/dynamic_membership b/dynamic_membership
@@ -0,0 +1,12 @@
+# Dynamic membership problem
+
+The [membership_problem] on [dynamic_data]
+
+- [dynamic_membership_word]
+- [dynamic_membership_trees]
+
+[dynamic_membership_extensions]
+
+See also: [dynamic_complexity], [pattern_matching], [incremental_maintenance], [dynamic_data_word], [pattern_matching_dynamic]
+
+Up: [incremental_maintenance]
diff --git a/dynamic_membership_regular b/dynamic_membership_regular
@@ -0,0 +1,9 @@
+# Dynamic membership regular
+
+The [dynamic_membership] problem for [regular_languages]
+
+[Academic_papers]:
+- [frandsen1997dynamic]
+- [amarilli2021dynamic]
+
+Up: [dynamic_membership], [regular_language]
diff --git a/dynamic_membership_word b/dynamic_membership_word
@@ -0,0 +1,13 @@
+# Dynamic membership word
+
+- [dynamic_membership_regular]
+- [incremental_maintenance_cfg]
+
+Depends on which [updates_word] are allowed
+
+[Generalizations]:
+- [incremental_parsing]
+- [dynamic_membership_restricted_edits]
+- for [regular_expressions_counting]: [bjorklund2015succinct]
+
+Up: [dynamic_membership], [dynamic_word]
diff --git a/dynamic_word b/dynamic_word
@@ -0,0 +1,9 @@
+# Dynamic word
+
+A [word] on which we can apply [updates_word]
+
+- [dynamic_membership_word]
+
+Up: [word]
+
+Aliases: dynamic words, dynamic string, dynamic strings
diff --git a/edge_deletion b/edge_deletion
@@ -3,3 +3,7 @@
[koch2024edge]
Up: [graph_modification]
+
+See also: [vertex_deletion]
+
+Aliases: edge removal
diff --git a/edit_distance_operations b/edit_distance_operations
@@ -0,0 +1,9 @@
+# Edit distance operations
+
+- [insertion]
+- [deletion]
+- [substitution]
+
+Up: [edit_distance], [update_word]
+
+See also: [levenshtein_distance]
diff --git a/eggans_theorem b/eggans_theorem
@@ -3,6 +3,6 @@
https://en.wikipedia.org/wiki/Star_height#Eggan's_theorem
https://en.wikipedia.org/wiki/Cycle_rank#Star_height_of_regular_languages
-[theorem]: The [star_height] of a [regular_language] L equals the minimum [cycle_rank] among all [automata_nondeterministic] with [epsilon_transition] accepting L.
+[theorem]: The [star_height] of a [regular_language] L equals the minimum [cycle_rank] among all [NFA_epsilon] accepting L.
Up: [theorem], [regular_language]
diff --git a/exponentiation b/exponentiation
@@ -2,7 +2,11 @@
- [graph_exponentiation]
- [exponentiation_by_squaring] or [fast_exponentiation]
+- [squaring]
+- [cubing]
Up: [mathematics_operation]
-See also: [exptime], [semigroup], [multiplication], [power_mathematics], [squaring], [square_root]
+See also: [exptime], [semigroup], [multiplication], [power_mathematics], [square_root]
+
+Aliases: exponent, exponents
diff --git a/fully_dynamic b/fully_dynamic
@@ -0,0 +1,9 @@
+# Fully dynamic
+
+Refers to [dynamic_data] which allow [update] featuring both [insertion] and [deletion] of elements
+
+[survey_paper]: [hanauer2022recent]
+
+Up: [update]
+
+See also: [dynamic_data]
diff --git a/graph_modification b/graph_modification
@@ -0,0 +1,14 @@
+# Graph modification
+
+An [update] on [graphs]
+
+- [edge_addition]
+- [edge_deletion]
+ - [eulerian_edge_deletion]
+- [vertex_deletion]
+
+- [graph_modification_problem]
+
+Up: [graph]
+
+See also: [graph_removal_lemma], [database_repairs]
diff --git a/graph_modification_problem b/graph_modification_problem
@@ -0,0 +1,8 @@
+# Graph modification problem
+
+[Computational_problems] that ask what is the minimum cost of performing [graph_modifications] on a [graph] to make it satisfy a property
+- cf survey [crespelle2023survey]
+
+- for [treewidth]: [graph_modification_treewidth]
+
+Up: [graph_modification]
diff --git a/logarithm b/logarithm
@@ -6,3 +6,5 @@
Up: [mathematics]
See also: [exponential], [logspace], [logarithmic]
+
+Aliases: logarithmic
diff --git a/logcfl b/logcfl
@@ -6,6 +6,8 @@ aka [nlogspace] with a [stack]
Also: [logdcfl] for [deterministic_context_free_grammar]
+[NL] is included in LOGCFL, and LOGCFL is included in [AC1], cf [buhrman2014computing] figure 1
+
Up: [complexity_class]
See also: [logcfl_complete]
diff --git a/nlogspace b/nlogspace
@@ -1,6 +1,6 @@
# NL
-[complexity_class] of [decision_problem] that can be solved by [nondeterministic] [turing_machine] with [logarithm] amount of memory
+[complexity_class] of [decision_problems] that can be solved by [nondeterministic] [turing_machine] with [logarithmic] amount of memory
Like [logspace] with [nondeterministic]
diff --git a/spanl b/spanl
@@ -4,6 +4,8 @@ Counting the number of *distinct* outputs of an [nl] [transducer]
Complete problem: [sharp_nfa]
+Defined in [alvarez1993very]
+
See also: [spanp]
Up: [complexity_class], [counting]
diff --git a/strongly_connected_component b/strongly_connected_component
@@ -9,4 +9,4 @@ Up: [graph]
See also: [biconnected_component], [connected_component], [strongly_connected]
-Aliases: SCC, strongly connected components
+Aliases: SCC, strongly connected components, SCCs
diff --git a/theorem b/theorem
@@ -23,6 +23,7 @@ A [result] in [mathematics], recognized as challenging to prove
- [Ladner's_theorem]
- [Mantel's_theorem]
- [Menger's_theorem]
+- [Nicomaque's_theorem]
- [Parikh's_theorem]
- [Prime_number_theorem]
- [Ramsey_theorem]
diff --git a/update b/update
@@ -7,7 +7,7 @@ Kinds of updates supported for [dynamic_data]:
- [substitution]
- [insertion]
- [deletion]
-- For [dynamic_data_graph]: [update_graph]
+- For [dynamic_data_graph]: [graph_modification]
- [edge_addition]
- [edge_deletion]
- In general
diff --git a/update_word b/update_word
@@ -11,6 +11,6 @@
Up: [update] for [word]
-See also: [dynamic_word]
+See also: [dynamic_word], [edit_distance_operations]
Aliases: updates word
diff --git a/vertex_deletion b/vertex_deletion
@@ -0,0 +1,5 @@
+# Vertex deletion
+
+Removing a [vertex] from a [graph], and doing [edge_removal] of all [edges] that are [incident] to the removed [vertex]
+
+Up: [graph_modification]
