wiki_research

commit 332948b05fe27a5b6b2f7d93306b4495a908ef90
parent e60d00f4b8121b5b4f31ee616b2f355bfc0c7e39
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Fri, 16 Oct 2026 11:52:54 +0200

commit with codex

Diffstat:
arboricity
 | 
4
++++
complexity_random
 | 
9
+++++----
edit_distance_graph
 | 
7
+++++++
language_unary
 | 
2
++
polynomial
 | 
1
+
polynomial_monic
 | 
7
+++++++
provenance_semiring_monus
 | 
5
+++++
semiring_with_monus
 | 
2
++

8 files changed, 33 insertions(+), 4 deletions(-)
diff --git a/arboricity b/arboricity
@@ -15,6 +15,10 @@ Connection between [arboricity] and [dynamic_data] in [lu2021towards]
 
 [bressan2022complexity]: optimality of the results of [chiba1985arboricity] for [graph_pattern_counting]
 
+[computational_complexity]: can be computed in [polynomial] time, cf
+https://en.wikipedia.org/wiki/Arboricity#Algorithms
+- and [linear_time] 2-[approximations]
+
 Up: [width_measure]
 
 See also: [degeneracy], [thickness], [pseudoarboricity]
diff --git a/complexity_random b/complexity_random
@@ -1,10 +1,11 @@
 # Randomized complexity class
 
 - [rl]: randomized [logspace]
-- [rp]
-- [bpp]
-- [zpp]
-  - [logspace] version [zplp]
+- [randomized_ptime]
+  - [rp]
+  - [bpp]
+  - [zpp]
+    - [logspace] version [zplp]
 
 No notion of [complete] problem for these classes (?)
 
diff --git a/edit_distance_graph b/edit_distance_graph
@@ -0,0 +1,7 @@
+# Graph edit distance
+
+https://en.wikipedia.org/wiki/Graph_edit_distance
+
+Up: [edit_distance], [graph]
+
+Aliases: graph edit distance
diff --git a/language_unary b/language_unary
@@ -2,6 +2,8 @@
 
 [Formal_language] over [unary_alphabet]
 
+- [language_unary_binarization]
+
 Up: [formal_language]
 
 Aliases: unary language, unary languages
diff --git a/polynomial b/polynomial
@@ -17,6 +17,7 @@ Concepts:
 - [monomial]
 - [polynomial_degree]
 - [root]
+- [polynomial_monic]
 
 Up: [mathematics]
 
diff --git a/polynomial_monic b/polynomial_monic
@@ -0,0 +1,7 @@
+# Monic polynomial
+
+A [polynomial] where the coefficient of the term of leading [polynomial_degree] is 1
+
+Up: [polynomial]
+
+Aliases: monic polynomial
diff --git a/provenance_semiring_monus b/provenance_semiring_monus
@@ -0,0 +1,5 @@
+# Provenance semiring monus
+
+[sen2026provenance]
+
+Up: [provenance], [semiring_with_monus]
diff --git a/semiring_with_monus b/semiring_with_monus
@@ -2,6 +2,8 @@
 
 A [semiring] that has a [monus]
 
+- [provenance_semiring_monus]
+
 Up: [semiring]
 
 Aliases: M semiring