commit a056f39b23a13d566adbf90670f0925555ea9428
parent 1ec2d3c9375094a078dbb3dbccb11f3aedf84b9c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 17 Oct 2025 21:36:57 +0200
Merge remote-tracking branch 'origin/master'
Diffstat:
27 files changed, 101 insertions(+), 11 deletions(-)
diff --git a/1_or_3_in_3_sat b/1_or_3_in_3_sat
@@ -9,3 +9,5 @@ https://cstheory.stackexchange.com/questions/53268/complexity-of-1-or-3-in-3-sat
Up: [schaefers_dichotomy_theorem], [sat_variants]
Aliases: 1 or 3 in 3SAT
+
+See also: [xor_sat]
diff --git a/automaton_complete b/automaton_complete
@@ -9,3 +9,5 @@ We can do [automaton_completion] to transform an [incomplete_automata] into a co
Up: [automata_types]
Aliases: complete automaton, complete automata
+
+See also: [automaton_trimmed]
diff --git a/automaton_trimming b/automaton_trimming
@@ -4,4 +4,6 @@ The process of transforming a [complete_automaton] into an [incomplete_automaton
Up: [automata_constructions]
-See also: [automaton_completion]
+See also: [automaton_completion], [automaton_trimmed]
+
+Aliases: pruning, automaton pruning, automata pruning, automata trimming, trimming
diff --git a/dynamic_membership_word b/dynamic_membership_word
@@ -9,6 +9,8 @@ Depends on which [updates_word] are allowed:
[Generalizations]:
- [incremental_parsing]
- [dynamic_membership_restricted_edits]
+- [dynamic_membership_conditional]
+- [dynamic_membership_append_only]
- for [regular_expressions_counting]: [bjorklund2015succinct]
Up: [dynamic_membership], [dynamic_word]
diff --git a/formal_language_separation b/formal_language_separation
@@ -13,6 +13,8 @@ Cases:
- [rat_rec_separability]
- [aut_rec_separability]
-See also: [barcelo2023separating]
+See also: [barcelo2023separating], [graph_sandwich_problem]
Up: [formal_language_theory]
+
+Aliases: language separation
diff --git a/formal_language_theory b/formal_language_theory
@@ -32,6 +32,7 @@ Studies [formal_languages]
## Problems
- [constrained_topological_sort]
+- [star_height_problem]
## Other notions
diff --git a/graph_family b/graph_family
@@ -20,6 +20,7 @@ A (generally [infinite]) set of [graphs]
- [strongly_connected_graph]
- [graph_series_parallel]
- [complete_graph]
+- [graph_hamiltonian]
- [chordal]
- [planar_graph]
diff --git a/graph_hamiltonian b/graph_hamiltonian
@@ -0,0 +1,9 @@
+# Hamiltonian graph
+
+A [graph] that has a [Hamiltonian_path] (or sometimes [Hamiltonian_cycle])
+
+For the [recognition_problem], see [Hamiltonian_path_problem]
+
+Up: [graph_family]
+
+Aliases: Hamiltonian graph, Hamiltonian graphs
diff --git a/graph_problem b/graph_problem
@@ -25,6 +25,7 @@
- [minimum_linear_arrangement]
- [graph_sandwich_problem]
- [planarity_testing]
+- [recognition_problem]
Up: [computational_problem] on [graph]
diff --git a/graph_sandwich_problem b/graph_sandwich_problem
@@ -0,0 +1,11 @@
+# Graph sandwich problem
+
+For a [graph_class] C, given two [graphs] (V, E_1) and (V, E_2) with E_1
+subseteq E_2, decide if there is E_1 subseteq E subseteq E_2 such that (V, E)
+belongs to C
+
+[CSP] approach in [bodirsky2025csp]
+
+Up: [graph_problem]
+
+See also: [language_separation]
diff --git a/graph_square b/graph_square
@@ -2,6 +2,8 @@
[graph_exponentiation] by 2 of [undirected_graph]
+Some are [Hamiltonian]: [graph_square_hamiltonian]
+
Up: [graph_exponentiation]
See also: [radoszewski2011hamiltonian], [graph_cube]
diff --git a/graph_square_hamiltonian b/graph_square_hamiltonian
@@ -0,0 +1,7 @@
+# Graph square hamiltonian
+
+An [undirected_graph] whose [graph_square] is a [Hamiltonian_graph]
+
+The [recognition_problem] is [NP_hard], cf https://en.wikipedia.org/wiki/Graph_power#Computational_complexity
+
+Up: [graph_square]
diff --git a/hamiltonian_cycle_cube b/hamiltonian_cycle_cube
@@ -3,3 +3,5 @@
The [graph_cube] of a [graph] always has a [Hamiltonian_cycle]
Up: [hamiltonian_cycle], [graph_cube]
+
+See also: [graph_square_hamiltonian]
diff --git a/hamiltonian_path b/hamiltonian_path
@@ -2,6 +2,8 @@
A [simple_path] that goes via all vertices of a [graph]
+A graph that has such a path is a [Hamiltonian_graph]
+
[Computational_problem]: [Hamiltonian_path_problem]
See also: [hamiltonian_cycle], [traveling_salesperson_problem], [k_path], [path_length], [eulerian_path]
diff --git a/hamiltonian_path_problem b/hamiltonian_path_problem
@@ -1,6 +1,6 @@
# Hamiltonian path problem
-The [computational_problem] of [deciding] whether an input [undirected_graph] has a [hamiltonian_path]
+The [computational_problem] of [deciding] whether an input [undirected_graph] is a [Hamiltonian_graph], i.e., has a [hamiltonian_path]
It is [np_complete], but it is [FPT] [parameterized] by [treewidth]:
- https://cs.stackexchange.com/questions/59325/an-fpt-algorithm-for-hamiltonian-cycle-running-parameterized-by-treewidth
diff --git a/horsetail_graph b/horsetail_graph
@@ -1,10 +1,10 @@
# Horsetail graph
-[Undirected_graphs] whose [graph_square] has [Hamiltonian_path]
+[Undirected_trees] that are [graph_square_hamiltonian]
Studied in [radoszewski2011hamiltonian]
-See also: [hamiltonian_cycle_cube], [graph_caterpillar]
+See also: [hamiltonian_cycle_cube], [graph_caterpillar], [graph_square]
Up: [graph_undirected]
diff --git a/idempotence b/idempotence
@@ -0,0 +1,14 @@
+# Idempotence
+
+- [function_idempotent]
+- [element_idempotent]
+- [Idempotent_semiring]
+ - [Semiring_n_idempotent]
+ - [additively_idempotent_semiring]
+ - [multiplicatively_idempotent_semiring]
+
+Up: [mathematics]
+
+See also: [involutivity]
+
+Aliases: idempotent
diff --git a/involution b/involution
@@ -6,4 +6,4 @@ A [function] which is its own [function_inverse]
Up: [function]
-See also: [Function_idempotent]
+See also: [Function_idempotent], [involutivity]
diff --git a/mathematics b/mathematics
@@ -9,7 +9,8 @@
- [canonicity]
- [paradox]
- [transitivity]
-- [idempotent]
+- [idempotence]
+- [involutivity]
- [dual]
- [finite]
- [infinite]
diff --git a/posbool b/posbool
@@ -2,6 +2,6 @@
Like [why_provenance], but imposing [absorptivity]
-Corresponds to [Boolean_formulas_positive] over the set of [provenance_tokens] seen as [variables]
+Corresponds to [positive_Boolean_formulas] over the set of [provenance_tokens] seen as [variables]
Up: [why_provenance]
diff --git a/ramsey_theorem b/ramsey_theorem
@@ -16,4 +16,4 @@ Up: [mathematics]
Aliases: Ramsey's theorem
-See also: [ward1994swell]
+See also: [ward1994swell], [Ramsey_theory]
diff --git a/regular_expression b/regular_expression
@@ -4,6 +4,11 @@ Operators: [regular_expression_operators]
Constructions: [conversion_automata]
+Notions:
+
+- [star_height]
+- [generalized_star_height]
+
[computational_problems]:
- [regular_expression_matching]
diff --git a/semiring_multiplicative_idempotent b/semiring_multiplicative_idempotent
@@ -5,3 +5,5 @@
Generalization: [semiring_n_idempotent]
Up: [semiring_idempotent]
+
+Aliases: multiplicatively idempotent semiring, semiring multiplicatively idempotent
diff --git a/subsequence b/subsequence
@@ -18,8 +18,10 @@
- [subsequence_automaton]
- [absent_subsequence]
- [subsequence_order]
+- [subword]
+- [subsequence_closed_language]
-See also: [subword], [sequence], [subword], [supersequence]
+See also: [subword], [sequence], [supersequence]
Up: [formal_language_theory], [stringology]
diff --git a/subsequence_closure b/subsequence_closure
@@ -0,0 +1,9 @@
+# Subsequence closure
+
+The *subsequence closure* of a [formal_language] L is the set of all [words] that are [subsequences] of a word of L
+
+By definition it is a [subsequence_closed_language]
+
+By [Higman's_lemma], the subsequence closure is always regular
+
+Up: [subword_closure]
diff --git a/subword b/subword
@@ -12,8 +12,10 @@ must be contiguous, unlike [subsequence]
- [subword_free_language]
- [subword_convex_language]
+- [subword_closure]
+
Up: [formal_language_theory]
-See also: [language_downwards_closed], [subword_universal], [factor], [compressed_subword_problem]
+See also: [language_downwards_closed], [subword_universal], [factor], [compressed_subword_problem], [subsequence_order]
Aliases: subwords
diff --git a/subword_closure b/subword_closure
@@ -0,0 +1,9 @@
+# Subword closure
+
+The *subword closure* of a [formal_language] L is the set of all [words] that are [subwords] of a word of L
+
+By definition it is a [subword_closed_language]
+
+Up: [subword]
+
+See also: [subsequence_closure]
