commit 711380e4c82d2293e47339b8b96add4a7d05b2cf
parent 36d0b1d54999d175de38de8ee7f21913fc34371f
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 28 May 2026 11:47:32 +0200
commit with codex
Diffstat:
15 files changed, 40 insertions(+), 11 deletions(-)
diff --git a/2cnf b/2cnf
@@ -6,6 +6,6 @@ A [conjunctive_normal_form] [boolean_formula] where every [clause] contains two
- generalization: [kcnf]
- special case: [monotone2cnf]
-Compilation to [OBDDs], cf [decolnet2026compilability]
+Compilation to [OBDDs], cf [decolnet2026compilability] with [phase_transitions]
Up: [conjunctive_normal_form]
diff --git a/automata_nondeterministic b/automata_nondeterministic
@@ -10,6 +10,8 @@ Special case: [automata_nondeterministic_dense]
Generalization: [epsilonNFA]
+Operations: [NFA_intersection]
+
Up: [one_way_automaton], [nondeterministic]
See also: [epsilon_transition]
diff --git a/automatic_relation b/automatic_relation
@@ -20,6 +20,6 @@ It is an [open_problem] whether the [computational_problem] of deciding [formal_
Up: [automata], [relation]
-See also: [automatic_structure], [automatic_graph], [sequence_automatic], [post_correspondence_problem]
+See also: [automatic_structure], [automatic_graph], [sequence_automatic], [post_correspondence_problem], [perfect_shuffle]
Aliases: automatic relations
diff --git a/automaton_intersection b/automaton_intersection
@@ -2,9 +2,8 @@
can be done with [product_construction]
-[computational_complexity] bounds on [automaton_emptiness] of intersection of constant number of [DFAs] (especially on [intersection_nonemptiness]): [oliveira2018intersection] and [oliveira2020fine]
-- connections to [3SUM] and [triangle_detection]
-- also [ascone2025are] on [regular_expressions] (for [intersection_nonemptiness])
+- [DFA_intersection]
+- [NFA_intersection]
Up: [automaton_constructions], [intersection]
diff --git a/counting_problem b/counting_problem
@@ -7,10 +7,10 @@
- [triangle_counting]
- [maximal_independent_set_counting]
- [subgraph_counting]
+ - [counting_simple_paths]
- [counting_query_answers]
- [counting_cqs]
- For [satisfiability_boolean]: [sharp_satisfiability]
-- [counting_simple_paths]
- [sharp_automaton]:
- [sharp_nfa], cf [arenas2020efficient]
- [sharp_ufa]
diff --git a/data_word b/data_word
@@ -1,10 +1,12 @@
# Data word
-like [word] but on an infinite or very large alphabet
+Like [words] but on an infinite or very large alphabet
-notions of [automaton]:
-- symbolic automata, written with a [logical_formula] on transitions
-- parametric automata: same but with a global parameter guesed at the beginning of the computation (existential)
+Notions of [automaton]:
+- [symbolic_automata], written with a [logical_formula] on transitions
+- [parametric_automata]: same but with a global parameter guesed at the beginning of the computation (existential)
- [register_automata]
Up: [word]
+
+Aliases: data words
diff --git a/datalog b/datalog
@@ -48,6 +48,7 @@
- [datalog_grounding]
- [datalog_rewriting]
- [datalog_course]
+- [datalog_conference]
Up: [query_language]
diff --git a/dfa_intersection b/dfa_intersection
@@ -0,0 +1,7 @@
+# DFA intersection
+
+[computational_complexity] bounds on [automaton_emptiness] of intersection of constant number of [DFAs] (especially on [intersection_nonemptiness]): [oliveira2018intersection] and [oliveira2020fine]
+- connections to [3SUM] and [triangle_detection]
+- also [ascone2025are] on [regular_expressions] (for [intersection_nonemptiness])
+
+Up: [automaton_intersection], [DFA]
diff --git a/dynamic_membership_word b/dynamic_membership_word
@@ -12,6 +12,7 @@ Depends on which [updates_word] are allowed:
- [dynamic_membership_conditional]
- [dynamic_membership_append_only]
- for [regular_expressions_counting]: [bjorklund2015succinct]
+- for [data_words]: [alpay2026support]
Up: [dynamic_membership], [dynamic_word]
diff --git a/graph_weighted b/graph_weighted
@@ -1,6 +1,6 @@
# Graph weighted
-A [graph] where [edges] carry [weight]
+A [graph] where [edges] carry [edge_weights]
[Graph_algorithms] to typically run on such graphs:
- [shortest_path]
diff --git a/nfa_intersection b/nfa_intersection
@@ -0,0 +1,8 @@
+# NFA intersection
+
+Can be done with the [product_construction]
+
+See [chistikov2026intersecting] for a more efficient algorithm in terms of the number of [transitions]
+- works via [perfect_shuffle]
+
+Up: [automaton_intersection], [NFA]
diff --git a/shortest_path b/shortest_path
@@ -12,6 +12,7 @@ Types:
Related:
- [shortest_path_practice]
+- [shortest_path_DAG]
Variants:
- [shortest_path_almost]
diff --git a/shortest_path_dag b/shortest_path_dag
@@ -0,0 +1,5 @@
+# Shortest path DAG
+
+The *shortest path DAG* for a [graph] G and [vertices] s and t is the [DAG] of the [vertices] and [edges] that can occur in a [shortest_path] between s and t (assuming positive [edge_weights])
+
+Up: [shortest_path]
diff --git a/shuffle b/shuffle
@@ -12,3 +12,5 @@ A [word] w is a *shuffle* of two [words] u and v if we can interleave the charac
Up: [formal_language_operator]
Aliases: interleaving
+
+See also: [perfect_shuffle]
diff --git a/threshold b/threshold
@@ -3,5 +3,6 @@
- [positive_threshold_function]
- [pqe_threshold]
- [locally_threshold_testable_language]
+- [phase_transition] in [random_graphs]
Up: [mathematics]
