commit 7a171c6bf15dff68bbb0f585b1f648d4ccfe849a
parent 73e82cb51c41a0cdbe448840354ce7fc3be75e1a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 4 Mar 2026 09:32:07 +0100
commit with codex
Diffstat:
9 files changed, 39 insertions(+), 5 deletions(-)
diff --git a/graph_h_minor_free b/graph_h_minor_free
@@ -12,4 +12,4 @@ Up: [graph_free]
See also: [graph_h_free]
-Aliases: H minor free, minor free, H minor free graph, H minor free graphs, excluded minor, graph excluding minor, graphs excluding minor, graph excluding minors
+Aliases: H minor free, minor free, H minor free graph, H minor free graphs, excluded minor, graph excluding minor, graphs excluding minor, graph excluding minors, H free graph, H free graphs
diff --git a/nfa_unary_lengths b/nfa_unary_lengths
@@ -11,4 +11,4 @@ An [NFA] which is [automata_unary], i.e., on a [unary_alphabet]
Up: [automata_unary], [nfa_acceptance]
-See also: [nfa_smallest_rejected]
+See also: [nfa_smallest_rejected], [Universality_automata_nondeterministic]
diff --git a/regular_expression_repetition b/regular_expression_repetition
@@ -3,4 +3,10 @@
e^{p,q}: repeat e between p and q times
- p and q written in binary (concise)
+Special case: [regular_expression_squaring]
+
+Problems:
+- [regular_expression_repetition_intersection_nonemptiness]
+- for [language_universality], cf [regular_expression_squaring_universality]
+
Up: [regular_expression_extensions]
diff --git a/regular_expression_repetition_intersection_nonemptiness b/regular_expression_repetition_intersection_nonemptiness
@@ -0,0 +1,5 @@
+# Regular expression repetition intersection nonemptiness
+
+it is [PSPACE_complete], cf https://cstheory.stackexchange.com/a/57014
+
+Up: [regular_expression_repetition], [Intersection_nonemptiness]
diff --git a/regular_expression_squaring b/regular_expression_squaring
@@ -2,6 +2,10 @@
[regular_expression] augmented with [squaring] operator
-makes [language_inclusion] and [language_universality] [EXPSPACE_complete], cf https://cstheory.stackexchange.com/a/40250
+makes [language_inclusion] and [language_universality] [EXPSPACE_complete], cf [regular_expression_squaring_universality]
+
+but [intersection_nonemptiness] still in [PSPACE], like for [regular_expression_repetition], cf [regular_expression_repetition_intersection_nonemptiness]
Up: [regular_expression], [squaring]
+
+See also: [regular_expression_repetition]
diff --git a/regular_expression_squaring_universality b/regular_expression_squaring_universality
@@ -0,0 +1,10 @@
+# Regular expression squaring universality
+
+It is [EXPSPACE_complete], cf https://cstheory.stackexchange.com/a/40250
+[meyer1972equivalence]
+
+Hence the same holds for [language_inclusion] and [language_equivalence]
+
+And the same holds for [regular_expression_repetition]
+
+Up: [language_universality], [regular_expression_squaring]
diff --git a/triangle_detection b/triangle_detection
@@ -13,6 +13,8 @@ https://en.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem
- cf [williams2018subcubic]
- cf https://people.csail.mit.edu/virgi/6.890/lecture2.pdf
+- [triangle_detection_hfree_graphs]
+
Up: [computational_problem] on [graph], [conjunctive_query], [fine_grained_complexity_problems]
See also: [all_edge_triangle], [boolean_matrix_multiplication], [sparse_triangle]
diff --git a/triangle_detection_hfree_graphs b/triangle_detection_hfree_graphs
@@ -0,0 +1,7 @@
+# Triangle detection in hfree graphs
+
+cf [abboud2026equivalent]
+
+Up: [triangle_detection], [H_free_graph]
+
+Aliases: Triangle detection in hfree graphs
diff --git a/universality_automata_nondeterministic b/universality_automata_nondeterministic
@@ -1,4 +1,4 @@
-# Universality automata nondeterministic
+# Universality for nondeterministic automata
[conp_complete] on [unary_alphabet] and [PSPACE_complete] otherwise:
- https://cs.stackexchange.com/a/97751
@@ -8,4 +8,4 @@ Omega(n 2^n): cf [ellul2005regular], Theorem 32
Up: [universality_automata], [automata_nondeterministic]
-Aliases: NFA universality
+Aliases: NFA universality, Universality for nondeterministic automata
