commit 68b7535cfa6b56b2e8302ea96d1245cd78d14b41
parent 52244a4e223a859566ecd072af6cf5c2c6cf0d07
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 26 Aug 2026 00:49:01 +0200
commit with codex
Diffstat:
30 files changed, 80 insertions(+), 53 deletions(-)
diff --git a/counter_automata_deterministic b/counter_automata_deterministic
@@ -1,5 +1,7 @@
-# Counter automata deterministic
+# Deterministic counter automata
for every *reachable* configuration (state, counter states), for every letter, there is at most one transition which is applicable (= whose guard is satisfied)
Up: [counter_automata_definition], [automata_deterministic]
+
+Aliases: deterministic counter automata, deterministic counter automaton
diff --git a/dahlhaus1994complexity b/dahlhaus1994complexity
@@ -1,4 +1,4 @@
-# Dahlhaus1994complexity
+# dahlhaus1994complexity
[academic_paper] about [submodular_minimization] and [network_flow]
diff --git a/database_instance b/database_instance
@@ -8,6 +8,6 @@ Can be considered in the [named_perspective] or in the [unnamed_perspective]
Up: [database_theory]
-Aliases: database, database instances, relational instance, relational instances, databases
+Aliases: database instances, relational instance, relational instances
See also: [instance], [subdatabase]
diff --git a/database_theory b/database_theory
@@ -11,6 +11,6 @@
- [query_semantics]
-See also: [databases], [database_startups], [description_logics], [finite_model_theory]
+See also: [databases], [description_logics], [finite_model_theory]
Up: [research_fundamental] of [database_research]
diff --git a/database_theory_techniques b/database_theory_techniques
@@ -1,7 +1,7 @@
# Database theory techniques
- [shredding], going from high arity to [arity_two]
-- [ucq_to_cq]
+- [UCQ_to_CQ]
- [tagging_trick]
Up: [database_theory]
diff --git a/deterministic_k_turn_pushdown_automata_equivalence b/deterministic_k_turn_pushdown_automata_equivalence
@@ -1,8 +1,10 @@
-# Deterministic k turn pushdown automata equivalence
+# Equivalence for Deterministic k turn pushdown automata
-- the [equivalence_problem] is [decidable], cf [valiant1974decidability]
-- subsumed by [senizergues1997equivalence] which shows [decidability] of [DPDA_equivalence]
+- the [equivalence_problem] is [decidable]
+ - cf [valiant1974decidability]
+- subsumed by [senizergues1997equivalence]
+ - shows [decidability] of [DPDA_equivalence]
Up: [language_equivalence_problem], [k_turn_pushdown_automata]
-Aliases: deterministic k turn PDA equivalence
+Aliases: deterministic k turn PDA equivalence, equivalence for Deterministic k turn pushdown automata
diff --git a/equivalence_automata_pushdown_deterministic b/equivalence_automata_pushdown_deterministic
@@ -1,4 +1,4 @@
-# Deterministic Pushdown Automaton Equivalence
+# Equivalence of deterministic pushdown automata
Was shown [decidable] by [senizergues1997equivalence]
@@ -8,6 +8,6 @@ Special case: [deterministic_k_turn_PDA_equivalence]
Up: [pushdown_automaton_deterministic], [automaton_equivalence]
-Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic, dpda equivalence, dpda equivalence problem, Deterministic Pushdown Automaton Equivalence
+Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic, DPDA equivalence, DPDA equivalence problem, Deterministic Pushdown Automaton Equivalence, equivalence of deterministic pushdown automata
See also: [context_free_grammar_unambiguous_equivalence_problem]
diff --git a/exact_matching b/exact_matching
@@ -1,4 +1,4 @@
-# Exact matching
+# Exact matching problem
- Input: [bipartite_graph] G with bicolored edges, integer k
- Output: does G contain a [perfect_matching] with exactly k red edges
diff --git a/extremal_graph_theory b/extremal_graph_theory
@@ -12,4 +12,4 @@ https://en.wikipedia.org/wiki/Extremal_graph_theory
- [forbidden_subgraph_problem]
-Up: [extremal_combinatorics] on [graph]
+Up: [extremal_combinatorics] on [graph], [graph_theory]
diff --git a/ganardi2024regular b/ganardi2024regular
@@ -1,4 +1,4 @@
-# Ganardi2024regular
+# ganardi2024regular
## Language classes
diff --git a/gelade2009regular b/gelade2009regular
@@ -1,8 +1,8 @@
-# Gelade2009regular
+# gelade2009regular
[regular_expression_repetition] operator
-not easy how to define [regular_expression_deterministic] with this operator
+not easy how to define [deterministic_regular_expressions] with this operator
[regular_expression_strongly_deterministic] is now useful because it makes it possible to store only one counter configuration
diff --git a/graph b/graph
@@ -36,9 +36,9 @@ See [graph_basic_notions]
## [Graph_algorithms]
-- [floyd_warshall]
-- [bellman_ford]
-- [dijkstras_algorithm]
+- [Floyd-Warshall]
+- [Bellman-Ford]
+- [Dijkstra's_algorithm]
## [Graph_families]
diff --git a/graph_basic_notions b/graph_basic_notions
@@ -34,7 +34,7 @@
- [incidence_graph]
- [balanced_separator]
- [graph_product]
-- [graph_empty]
+- [empty_graph]
Up: [graph]
diff --git a/graph_empty b/graph_empty
@@ -1,4 +1,4 @@
-# Graph empty
+# Empty graph
A [graph] with no [edges], or sometimes the graph with no [edges] and no [vertices]
diff --git a/graph_product b/graph_product
@@ -1,9 +1,11 @@
# Graph product
+There are different notions of [product] on [graphs]:
+
- [graph_direct_product]
- - [chromatic_number] is at most the min of the chromatic number of the arguments and the inequality can be strict [shitov2019counterexamples]
- [graph_cartesian_product]
- - [chromatic_number] is the sum of the two chromatic numbers: [Sabidussi's_theorem]
- [graph_strong_product] in [dujmovic2025grid]
+[graph_product_chromatic_number]
+
Up: [graph_basic_notions]
diff --git a/graph_product_chromatic_number b/graph_product_chromatic_number
@@ -0,0 +1,9 @@
+# Graph product chromatic number
+
+- [graph_direct_product]
+ - the [chromatic_number] is at most the min of the chromatic number of the arguments
+ - and the inequality can be strict [shitov2019counterexamples]
+- [graph_cartesian_product]
+ - the [chromatic_number] is the sum of the two chromatic numbers: [Sabidussi's_theorem]
+
+Up: [graph_product], [chromatic_number]
diff --git a/greenlaw1995limits b/greenlaw1995limits
@@ -1,7 +1,7 @@
-# Greenlaw1995limits
+# greenlaw1995limits
https://homes.cs.washington.edu/~ruzzo/papers/limits.pdf
-discusses [p_complete] as a limit to [parallelism]
+discusses [P_completeness] as a limit to [parallelism]
Up: [books] on [p_complete]
diff --git a/integer_linear_program b/integer_linear_program
@@ -2,6 +2,6 @@
Like a [linear_program] but the [variables] must be [integers]
-Up: [integer_linear_programming]
+Solving them: [integer_linear_programming]
See also: [mixed_integer_linear_program]
diff --git a/karmakar2024expected b/karmakar2024expected
@@ -1,5 +0,0 @@
-# Karmakar2024expected
-
-by [senellart] and [mikael]
-
-Up: [academic_paper] about [shapley_value_expected]
diff --git a/matching b/matching
@@ -8,6 +8,8 @@ Structure in [graphs] and [bipartite_graphs]: a subset of [edges] where no two [
[Computational_problems]:
- [matching_problem]
+ - [maximum_matching_problem]
+ - [perfect_matching_problem]
- [exact_matching_problem]
- [matching_counting]
- [maximum_matching_counting]
@@ -20,7 +22,6 @@ Variants:
- [matching_variants]
- [induced_matching]
-- [exact_matching]
Also the [linear_relaxation]: see [fractional_edge_packing]
diff --git a/matching_problem b/matching_problem
@@ -0,0 +1,7 @@
+# Matching problem
+
+- [maximum_matching_problem]
+- [perfect_matching_problem]
+- [exact_matching_problem]
+
+Up: [matching], [computational_problem]
diff --git a/maximum_independent_set_bipartite b/maximum_independent_set_bipartite
@@ -1,8 +1,10 @@
-# Maximum independent set bipartite
+# Maximum independent set on bipartite graphs
-finding [maximum_independent_set] in [graph_bipartite]
+The [computation_problem] of finding a [maximum_independent_set] in a [bipartite_graph]
-- complement of a [maximum_independent_set] is [minimum_vertex_cover]
-- and then problem can be solved by [minimum_vertex_cover_bipartite]
+- the complement of a [maximum_independent_set] is a [minimum_vertex_cover]
+- and then the problem can be solved by [minimum_vertex_cover_bipartite]
-Up: [maximum_independent_set], [graph_bipartite]
+Up: [maximum_independent_set_problem], [graph_bipartite]
+
+Aliases: Maximum independent set on bipartite graphs
diff --git a/monet2020solving b/monet2020solving
@@ -1,4 +1,4 @@
-# Monet2020solving
+# monet2020solving
- [hasse_diagram] of the [hk_queries], where only the bottom element is a zero of the [mobius_function]
- [q9] query
diff --git a/monoid_positive b/monoid_positive
@@ -1,4 +1,4 @@
-# Monoid positive
+# Positive monoid
A [monoid] being *positive* means x + y = 0 implies x = 0 and y = 0
@@ -7,3 +7,5 @@ aka "zero-sum-free"
See also: [semiring_positive]
Up: [monoid]
+
+Aliases: positive monoid, positive monoids
diff --git a/pushdown_automaton_deterministic b/pushdown_automaton_deterministic
@@ -1,10 +1,8 @@
-# Pushdown automaton deterministic
+# Deterministic pushdown automaton
- [universality_automata_pushdown_deterministic]
- [equivalence_automata_pushdown_deterministic]
Up: [pushdown_automaton]
-Aliases: deterministic pushdown automaton
-
-Aliases: DPDA, DPDAs
+Aliases: DPDA, DPDAs, deterministic pushdown automaton, deterministic pushdown automata
diff --git a/relation b/relation
@@ -13,3 +13,5 @@ Axioms:
- [antisymmetric_relation]
Up: [mathematics]
+
+Aliases: relations
diff --git a/universality_automata_deterministic b/universality_automata_deterministic
@@ -1,9 +1,9 @@
-# Universality automata deterministic
+# Universality for deterministic automata
In [ptime] via [automaton_complementation]
-Generalizes to [universality_automata_pushdown_deterministic]
+Generalizes to [universality_of_deterministic_pushdown_automata]
Up: [universality_automata], [automaton_deterministic]
-Aliases: DFA universality
+Aliases: DFA universality, universality for deterministic automata, universality for deterministic automaton
diff --git a/universality_automata_pushdown b/universality_automata_pushdown
@@ -1,6 +1,9 @@
-# Universality automata pushdown
+# Universality for pushdown automata
-- [universality_automata_pushdown_nondeterministic] is [undecidable]
-- [universality_automata_pushdown_deterministic]
+- [universality_for_nondeterministic_pushdown_automata]
+ - it is [undecidable]
+- [universality_for_deterministic_pushdown_automata]
Up: [universality_automata], [pushdown_automata]
+
+Aliases: universality for pushdown automata
diff --git a/universality_automata_pushdown_deterministic b/universality_automata_pushdown_deterministic
@@ -1,11 +1,11 @@
-# Universality automata pushdown deterministic
+# Universality of deterministic pushdown automata
-It is in [PTIME], like [Universality_automata_deterministic]
+It is in [PTIME], like [universality_of_deterministic_automata]
cf https://cstheory.stackexchange.com/questions/55099/the-complexity-of-the-universality-problem-for-deterministic-pushdown-automata
Up: [universality_automata_pushdown], [Automata_pushdown_deterministic]
-Aliases: DPDA universality
+Aliases: DPDA universality, universality of deterministic pushdown automata, universality of deterministic pushdown automaton, universality for deterministic pushdown automata, universality for deterministic pushdown automaton,
See also: [universality_automata_pushdown_nondeterministic]
diff --git a/universality_automata_pushdown_nondeterministic b/universality_automata_pushdown_nondeterministic
@@ -1,7 +1,9 @@
-# Universality automata pushdown nondeterministic
+# Universality for nondeterministic pushdown automata
It is [undecidable] cf https://cstheory.stackexchange.com/questions/55099/the-complexity-of-the-universality-problem-for-deterministic-pushdown-automata
Up: [universality_automata_pushdown], [pushdown_automaton_nondeterministic]
See also: [universality_automata_pushdown_deterministic]
+
+Aliases: universality for nondeterministic pushdown automata, universality for nondeterministic pushdown automaton
