commit 12d718341c043071c15e707113db981e68b69290
parent 365e0ecd7457e8c9c99a4afb27c9eb31f6cfb8ed
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 16 Feb 2026 00:07:33 +0100
Merge remote-tracking branch 'origin/master'
Diffstat:
10 files changed, 42 insertions(+), 8 deletions(-)
diff --git a/buchis_theorem b/buchis_theorem
@@ -2,8 +2,10 @@
https://en.wikipedia.org/wiki/B%C3%BCchi-Elgot-Trakhtenbrot_theorem
-Equivalence of [monadic_second_order_logic] and of [regular_languages] on [words]
+Equivalence of [monadic_second_order_logic] and of [regular_languages] for [logic_on_words]
Up: [theorem] in [formal_language_theory]
See also: [Büchi_automaton]
+
+Aliases: Büchi Elgot Trakhtenbrot theorem
diff --git a/graph_exact_distance_square b/graph_exact_distance_square
@@ -1,6 +1,6 @@
# Graph exact distance square
-Given a [graph] G, the *exact square* of G is a graph G' on the same [vertices] where you connect each pair of vertices that are connected by a [walk] of length exactly 2
+Given a [graph] G, the *exact square* of G is a graph G' on the same [vertices] where you connect each pair of vertices that are at [distance] exactly 2
[graph_exact_distance_square_root_problem]
diff --git a/independent_set b/independent_set
@@ -19,11 +19,7 @@ An *independent set* is a [subset] of [vertices] of an [undirected_graph] such t
## [counting]
-- [sharp_bis] is the problem of counting independent sets on [graph_bipartite]
- - it is open whether it admits an [fpras]
-- [dyer1999counting]: on general graphs there is no [fpras], cf [sharp_is]
-
-By [duality], counting independent sets exactly is the same as counting [vertex_cover] exactly
+[independent_set_counting]
## [linear_relaxation]
diff --git a/independent_set_counting b/independent_set_counting
@@ -0,0 +1,11 @@
+# Independent set counting
+
+- [sharp_bis] is the problem of counting independent sets on [bipartite_graphs]
+ - it is open whether it admits an [fpras]
+- [dyer1999counting]: on general graphs there is no [fpras], cf [sharp_is]
+
+By [duality], counting independent sets exactly is the same as counting [vertex_cover] exactly
+
+Up: [counting_problem], [independent_set]
+
+See also: [maximal_independent_set_counting], [maximum_independent_set_counting]
diff --git a/logic_over_words b/logic_over_words
@@ -0,0 +1,14 @@
+# Logic over words
+
+Writing, e.g., [FO] and [MSO] over [words]
+
+The [signature] includes:
+
+- [order] on positions
+- testing if a position has a specific [letter]
+
+Up: [logic], [word]
+
+See also: [monotone_first_order_logic], [Büchi's_theorem]
+
+Aliases: logic on words
diff --git a/maximal_independent_set_counting b/maximal_independent_set_counting
@@ -5,5 +5,8 @@
- mentioned in [livshits2021counting]
- [sharpp_hard] even on [chordal_graphs]:
- [okamoto2008counting]
+- [approximate_counting]: cf [goldberg2016approximately] on [bipartite_graphs]
Up: [counting_problem], [maximal_independent_set]
+
+See also: [maximum_independent_set_counting], [independent_set_counting]
diff --git a/query_resilience b/query_resilience
@@ -53,6 +53,8 @@ Generalization:
- [deletion_propagation_with_source_side_effects]
+Old related work: [yannakakis1981edge]
+
Up: [database_theory]
See also: [pqe], [minimal_witness]
diff --git a/st_reliability b/st_reliability
@@ -6,6 +6,7 @@ Can be posed on [directed_graphs] and [undirected_graphs]
- [st_reliability_approximation]
- [st_reliability_provenance]
+- [st_reliability_planar]
Up: [network_reliability]
diff --git a/st_reliability_planar b/st_reliability_planar
@@ -0,0 +1,5 @@
+# St-reliability planar
+
+Also [sharpP_complete], cf [provan1986complexity]
+
+Up: [st_reliability], [planar_graphs]
diff --git a/word b/word
@@ -27,6 +27,6 @@ Special cases:
Up: [formal_language_theory]
-See also: [update_word], [sequence], [text_algorithms], [endmarker]
+See also: [update_word], [sequence], [text_algorithms], [endmarker], [logic_over_words]
Aliases: words, string, strings
