commit fbc26a76061326dbd50de3c40c52c6b7e87aad26
parent bfa0a5e71912753761258733efc303e1615b6fc5
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 6 Sep 2025 22:35:58 +0200
commit with codex
Diffstat:
20 files changed, 76 insertions(+), 33 deletions(-)
diff --git a/1_critical b/1_critical
@@ -1,7 +1,7 @@
# 1 critical
-The [structure] with a single [domain_element] and every [relation] contains only the [tuple] mentioning only that element
+The *1 critical* [structure] is the [structure] with a single [domain_element] and every [relation] contains only the [tuple] mentioning only that element
-aka "well of positivity" in [gogacz2014all]
+Called the "well of positivity" in [gogacz2014all]
-Up: [dependency_expressiveness]
+Up: [structure]
diff --git a/1_or_3_in_3_sat b/1_or_3_in_3_sat
@@ -1,9 +1,11 @@
-# 1_or_3_in_3_sat
+# 1-or-3-in-3SAT
-Variant of [satisfiability_boolean] where each clause contains exactly 3 literals and you want a valuation such that each clause has 1 or 3 true literals
+The *1-or-3-in-3SAT* [decision_problem] is the variant of [Boolean_satisfiability] where each [clause] contains exactly 3 [literals] and where the [decision_problem] asks whether there exists a [Boolean_valuation] such that each [clause] contains exactly 1 or 3 [literals] that evaluate to true
-It is in fact [ptime] because it is [affine]
+This [decision_problem] is in fact in [PTIME] because it is [affine]
https://cstheory.stackexchange.com/questions/53268/complexity-of-1-or-3-in-3-sat-odd-3-sat
Up: [schaefers_dichotomy_theorem], [sat_variants]
+
+Aliases: 1 or 3 in 3SAT
diff --git a/2_ambiguous_cfg b/2_ambiguous_cfg
@@ -1,7 +1,7 @@
-# 2 ambiguous CFG
+# 2-ambiguous CFG
-An [ambiguous_CFG] where every [word] has at most two [parse_trees]
+A *2-ambiguous CFG* is an [ambiguous_CFG] where every [word] has at most two [parse_trees]
Up: [degree_of_ambiguity_cfg]
-Aliases: 2 ambiguous CFGs
+Aliases: 2 ambiguous CFGs, 2ambiguous CFG, 2ambiguous CFGs
diff --git a/arity b/arity
@@ -6,3 +6,5 @@
[amarilli2015combining]
Up: [logic]
+
+Aliases: Arity (relation)
diff --git a/cartesian_product b/cartesian_product
@@ -1,6 +1,6 @@
# Cartesian product
-The *cartesian products* of two [sets] S and T is the [set] of [ordered_pairs]
+The *cartesian product* of two [sets] S and T is the [set] of [ordered_pairs]
- (s, t) with s in S and t in T
Up: [mathematics]
diff --git a/combinatorics b/combinatorics
@@ -6,13 +6,14 @@
- [extremal_combinatorics]
- [word_combinatorics]
-## Results
+## [Theorems]
- [ramsey_turan_theory]
- [ramsey_theorem]
- [sunflower_lemma]
- [higmans_lemma]
-- erdos-szekeres theorem on the existence of nonincreasing/nondecreasing [subsequence] of size sqrt(n) in a sequence of length n
+- [erdos_szekeres_theorem]
+ - existence of nonincreasing/nondecreasing [subsequence] of size sqrt(n) in a [sequence] of length n
## Techniques
@@ -20,14 +21,14 @@
## Specific problems/objects
-- [universal_tree] https://games-automata-play.github.io/blog/universal_trees/
+- [universal_tree]
- [sparse_rulers]
- [golomb_ruler] / [sidon_set]
- sequences without [arithmetic_progressions]
- [salem_spencer_set]
- [angel_problem]
- [german_tank_problem]
- - frequentist interpretation vs bayesian interpretatino
+ - frequentist interpretation vs bayesian interpretation
- [superpermutation]
- [social_golfer_problem]
- [menage_problem]
diff --git a/computational_problem b/computational_problem
@@ -28,7 +28,8 @@
## Specific problems
- [clique_problem]
-- [constraint_satisfaction_problem_tractability]
+- [constraint_satisfaction_problem]
+ - [constraint_satisfaction_problem_tractability]
- [graph_problem]
- [maximum_matching_problem]
- [minimum_formula_size_problem]
diff --git a/conjunctive_query_full b/conjunctive_query_full
@@ -1,4 +1,4 @@
-# Conjunctive query full
+# Full conjunctive query
A [CQ] without [projection]; also called a [join] query
diff --git a/database_instance b/database_instance
@@ -2,10 +2,12 @@
A set of [relations] containing [tuples] or [facts], for the [relations] defined in a [relational_signature]
-[named_perspective] vs [unnamed_perspective]
+This is like a [structure_(logic)] but the [relational_signature] is already fixed, and the [domain] is usually taken in the [active_domain] semantics
+
+Can be considered in the [named_perspective] or in the [unnamed_perspective]
Up: [database_theory]
-Aliases: database, database instances
+Aliases: database, database instances, relational instance, relational instances, databases
See also: [instance], [subdatabase]
diff --git a/domain_element b/domain_element
@@ -0,0 +1,5 @@
+# Domain element
+
+A *domain element* is an element of the [domain] of a [structure] or of a [relational_instance]
+
+Up: [logic]
diff --git a/domino_problem b/domino_problem
@@ -0,0 +1,8 @@
+# Domino problem
+
+- [esperet2024structure]
+- [auburn2018domino]
+
+Up: [graph_problem]
+
+See also: [enumeration_core]
diff --git a/erdos_szekeres_theorem b/erdos_szekeres_theorem
@@ -0,0 +1,5 @@
+# Erdos-Szekeres theorem
+
+https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem
+
+Up: [combinatorics]
diff --git a/higmans_lemma b/higmans_lemma
@@ -1,8 +1,8 @@
# Higman's lemma
-[words] on finite [alphabet] are [well_quasi_ordering] by [subsequence] relation
+The [words] on a finite [alphabet] are [well_quasi_ordered] by the [subsequence] [relation]
-Of course does not work with [subword]
+Of course this does not work with the [subword] [relation], e.g., a b* c
Up: [lemma], [word_combinatorics]
diff --git a/input b/input
@@ -0,0 +1,5 @@
+# Input
+
+The specification of what a [computational_problem] is given
+
+Up: [computational_problem]
diff --git a/instance b/instance
@@ -0,0 +1,5 @@
+# Instance
+
+A choice of values for the [input] to a [computational_problem]
+
+Up: [computational_problem]
diff --git a/output b/output
@@ -0,0 +1,5 @@
+# Output
+
+The specification of what a [computational_problem] must return
+
+Up: [computational_problem]
diff --git a/structure b/structure
@@ -0,0 +1,12 @@
+# Structure
+
+A [structure] consists of a [domain] D, a [relational_signature] σ, and an interpretation giving, for each [relation] of σ of [arity_(relation)] k, a set of k-tuples that are those for which the relation holds
+
+- [substructure]
+- [reduct]: the [substructure] which is the restriction of a [structure] to a subset of the [signature]
+
+Up: [logic]
+
+See also: [relational_instance]
+
+Aliases: structure (logic)
diff --git a/superpermutation b/superpermutation
@@ -10,8 +10,8 @@ Related notion: [universal_word] (all contiguous factors)
Related notion: shortest word containing all permutations as a [subsequence]
- discussed here https://mathoverflow.net/questions/165303/shortest-supersequence-of-all-permutations-of-n-elements
- - on [oeis] https://oeis.org/A062714
- - article surveying this: https://www.tandfonline.com/doi/full/10.1080/00029890.2021.1835384#d1e3032
+ - on [OEIS] https://oeis.org/A062714
+ - article surveying this: [engen2021containing]
- lower bound [kleitman1976lower]
- [conp_hard] to detect, cf [uznanski2015all] by [przemyslaw]
- from https://cstheory.stackexchange.com/questions/31559/recognizing-sequences-with-all-permutations-of-1-ldots-n-as-subsequence
diff --git a/word_combinatorics b/word_combinatorics
@@ -5,6 +5,6 @@
- [universal_word]
- [de_bruijn_sequence]
-Up: [combinatorics] on [word]
+Up: [combinatorics] on [words]
See also: [stringology], [formal_language_theory]
diff --git a/zivny2009expressive b/zivny2009expressive
@@ -1,10 +0,0 @@
-# zivny2009expressive
-
-[submodular_set_function_bounded_arity], a sum of [submodular_set_functions] defined on a bounded subset of [variables]
-
-talks about [submodular_polynomial], and quadratic submodular polynomials, which admit a more efficient optimization algorithm by reduction to [min_cut]
-
-all cubic submodular polynomials can be expressed as quadratic submodular polynomials, but for degree-4 this is no longer true and they characterize which ones are expressible
-- the [computational_complexity] of recognizing them is open
-
-Up: [academic_paper] on [submodular_set_function]
