wiki_research

commit 989be652403bf77f37c27fb6c3393db7562977c2
parent 599aaf0b0f224a29986521a018be91aea088245a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Sun, 29 Dec 2024 16:28:29 +0100

commit with codex

Diffstat:
amplification_technique
 | 
2
++
blocking_factor
 | 
4
+++-
complexity_space
 | 
2
+-
complexity_time
 | 
7
+++++++
datalogpm
 | 
2
++
hypergraph
 | 
2
++
incremental_time
 | 
2
++

7 files changed, 19 insertions(+), 2 deletions(-)
diff --git a/amplification_technique b/amplification_technique
@@ -7,3 +7,5 @@ cf git/reading-group/notes/non-approximability.txt
 [marcelo]: This is a reference for the amplification technique:Alistair Sinclair: Algorithms for random generation and counting - a Markov chain approach. Progress in theoretical computer science, Birkhäuser 1993, ISBN 978-0-8176-3658-6, pp. 1-146
 
 See also: [interpolation_method]
+
+Up: [research_technique]
diff --git a/blocking_factor b/blocking_factor
@@ -1,6 +1,6 @@
 # Blocking factor
 
-Blocking factor of [language] is [word] which never occurs as [factor] of a [word] of the language
+A blocking factor of a [language] is a [word] which never occurs as a [factor] of a [word] of the language
 
 - [blocking_factor_minimal]
 - [blocking_sequence]
@@ -14,3 +14,5 @@ even for [strongly_connected] [NFA], it's [PSPACE_complete]
 See also: [links_seminar_gabriel], [property_testing]
 
 Aliases: blocking factors
+
+Up: [word]
diff --git a/complexity_space b/complexity_space
@@ -2,6 +2,6 @@
 
 - [savitchs_theorem]: we can simulate [nondeterministic] machine with quadratic blowup in space
 
-Up: [complexity]
+Up: [complexity_measure]
 
 See also: [complexity_time]
diff --git a/complexity_time b/complexity_time
@@ -0,0 +1,7 @@
+# Complexity time
+
+The [asymptotic] running time of an [algorithm]
+
+Up: [complexity_measure]
+
+See also: [complexity_space]
diff --git a/datalogpm b/datalogpm
@@ -5,3 +5,5 @@ cf [cali2010datalog]
 Fragment: [warded_datalogpm]
 
 See also: [tuple_generating_dependency], [datalog], [georg_gottlob]
+
+Up: [datalog]
diff --git a/hypergraph b/hypergraph
@@ -28,4 +28,6 @@ generalizes [graph]
 
 See also: [generalized_hypertree_width], [conjunctive_query], [relational_instance], [simplicial_complex]
 
+Up: [data_structure], [computer_science]
+
 Aliases: hypergraphs
diff --git a/incremental_time b/incremental_time
@@ -3,3 +3,5 @@
 Discussed in [capelli2023geometric]
 
 See also: [enumeration]
+
+Up: [complexity_measure]