commit 3bf6ac13b95d55b225d89a9b6e08d702c12c9d4f
parent 469e63d05bd2d80e4bedaac9d35231a7202ed3cf
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sun, 3 Aug 2025 23:31:21 +0200
commit with codex
Diffstat:
30 files changed, 140 insertions(+), 5 deletions(-)
diff --git a/algebraic_structure b/algebraic_structure
@@ -3,6 +3,7 @@
- [monoid]
- [semigroup]
- [group]
+- [2_monoid]
- [semiring]
- [ring]
- [field]
diff --git a/atom b/atom
@@ -7,3 +7,5 @@ notion of an atom in logic
See also: [vector_addition_system], [data_word]
Up: [logic]
+
+Aliases: atoms
diff --git a/boolean_sjfcq b/boolean_sjfcq
@@ -0,0 +1,7 @@
+# Boolean SJFCQ
+
+A [SJFCQ] which is a [boolean_query]
+
+Up: [sjfcq], [boolean_query]
+
+Aliases: boolean SJFCQs
diff --git a/champarnaud1989maxmin b/champarnaud1989maxmin
@@ -0,0 +1,5 @@
+# champarnaud1989maxmin
+
+They study the subsets of {0,1}^n where the [state_complexity] (number of [states] needed by a [DFA]) is maximal, and show that it is of the order of 2^n/n
+
+Up: [academic_paper] about [knowledge_compilation_automata]
diff --git a/commutativity b/commutativity
@@ -0,0 +1,11 @@
+# Commutativity
+
+"Commutativity" means xy=yx
+
+- [commutative_semiring]
+- [commutative_closure]
+- [commutative_language]
+
+Up: [mathematics]
+
+See also: [order], [order_invariant], [central_element]
diff --git a/decidable b/decidable
@@ -0,0 +1,7 @@
+# Decidable
+
+A [computational_problem] for which there exists an [algorithm] as a [Turing_machine]
+
+Up: [decidability]
+
+See also: [undecidable]
diff --git a/free_variable b/free_variable
@@ -0,0 +1,5 @@
+# Free variable
+
+A [variable] to which no [quantifier] apply, e.g., part of the output of a [query]
+
+Up: [variable]
diff --git a/knowledge_compilation b/knowledge_compilation
@@ -7,6 +7,7 @@ Classes of [circuit] ensuring tractability
- [query_compilation]: knowledge compilation on the [provenance] of a query
- [constraint_satisfaction_problem_knowledge_compilation]
- [knowledge_compilation_query]: the type of questions asked on circuits
+- [knowledge_compilation_automata]
[circuit_bounds_vs_complexity_bounds]
diff --git a/knowledge_compilation_automata b/knowledge_compilation_automata
@@ -0,0 +1,10 @@
+# Knowledge compilation automata
+
+The use of [automata] as [knowledge_compilation] formalisms
+- automata correspond to [BDDs] but the [variable_order] is usually fixed in advance
+- [circuit_circus]
+- [cstheory] question: https://cstheory.stackexchange.com/questions/53719/relationship-between-size-of-boolean-functions-and-dfas
+ - cites [champarnaud1989maxmin]
+ - cites [kjoshanssen2021vc] which relates to [vc_dimension]
+
+Up: [knowledge_compilation], [automata]
diff --git a/length_universality_automata b/length_universality_automata
@@ -0,0 +1,7 @@
+# Length universality automata
+
+[computational_problem] on [automata] studied in [gawrychowski2020existential]: given an [automaton], is there an integer l such that Sigma^l is included in the language?
+- for [NFA] this is [NEXPTIME_complete] and the smallest l can be doubly exponential in the number of states
+- for [NFA] for a given l this is [PSPACE_complete]
+
+Up: [computational_problem], [universality_automata]
diff --git a/logarithm b/logarithm
@@ -7,4 +7,4 @@ Up: [mathematics]
See also: [exponential], [logspace], [logarithmic]
-Aliases: logarithmic
+Aliases: logarithmic, logarithms
diff --git a/polylogarithmic b/polylogarithmic
@@ -0,0 +1,5 @@
+# Polylogarithmic
+
+A [polynomial] of [logarithms]
+
+Up: [logarithm]
diff --git a/polynomial_multilinear b/polynomial_multilinear
@@ -7,3 +7,5 @@ For polynomials with just one [variable], you get an [affine_function]
Up: [polynomial]
See also: [trio]
+
+Aliases: multilinear polynomial, multilinear polynomials
diff --git a/pspace b/pspace
@@ -3,6 +3,7 @@
https://en.wikipedia.org/wiki/PSPACE
- [PSPACE_complete]
+- [pspace_hard]
Up: [complexity_class]
diff --git a/pspace_complete b/pspace_complete
@@ -0,0 +1,5 @@
+# PSPACE complete
+
+The class of [computational_problems] that are in [PSPACE] and [PSPACE_hard]
+
+Up: [pspace]
diff --git a/query b/query
@@ -15,4 +15,4 @@ Up: [database_theory]
Aliases: queries
-See also: [knowledge_compilation_query], [query_match]
+See also: [knowledge_compilation_query], [query_match], [query_answer]
diff --git a/query_answer b/query_answer
@@ -0,0 +1,7 @@
+# Query answer
+
+A [tuple] (named in [named_perspective], unnamed in [unnamed_perspective]) of [constants] that make a [query] true, i.e., substituting the [free_variables] of the [query] by these constants yields a [query] which evaluates to true
+
+Up: [query]
+
+Aliases: query answers
diff --git a/ramsey_theorem b/ramsey_theorem
@@ -15,3 +15,5 @@ Can also be useful in [formal_language_theory]: [ramsey_formal_languages]
Up: [mathematics]
Aliases: Ramsey's theorem
+
+See also: [ward1994swell]
diff --git a/semiring_commutative b/semiring_commutative
@@ -5,3 +5,5 @@ A [semiring] where [product] is [commutative]
Up: [semiring], [commutative]
See also: [monoid_commutative]
+
+Aliases: commutative semiring, commutative semirings
diff --git a/semiring_distributivity_axiom b/semiring_distributivity_axiom
@@ -0,0 +1,7 @@
+# Semiring distributivity axiom
+
+The [axiom] that [product] [distributes] over [sum], which is part of the definition of [semirings]
+
+Up: [distributivity], [semiring]
+
+See also: [2_monoid]
diff --git a/semiring_finite b/semiring_finite
@@ -0,0 +1,5 @@
+# Semiring finite
+
+A [semiring] which is [finite]
+
+Up: [semiring], [finite]
diff --git a/set_semantics b/set_semantics
@@ -0,0 +1,7 @@
+# Set semantics
+
+The semantics where [queries] return a [set] of [query_answers], i.e., without [duplicates]
+
+Up: [database_theory_concepts]
+
+See also: [bag_semantics]
diff --git a/shapley_value b/shapley_value
@@ -13,4 +13,6 @@ Results:
- [shapley_value_omqa]
+[Computational_problem]: [Shapley_value_computation]
+
See also: [pqe], [explainability], [shap_score], [stable_marriage]
diff --git a/sjfcq b/sjfcq
@@ -4,7 +4,9 @@
[dichotomy] for [pqe] in [dalvi2007efficient]
-Special case: [acyclic_SJFCQ]
+Special cases:
+- [acyclic_SJFCQ]
+- [boolean_SJFCQ]
Up: [conjunctive_query], [self_join]
diff --git a/submodular_set_function b/submodular_set_function
@@ -7,6 +7,8 @@ whenever X \subseteq Y
Implies being [subadditive], converse is not true in general
+Special case discussed in [zivny2009expressive]: [submodular_set_function_bounded_arity], a sum of [submodular_set_functions] defined on a bounded subset of variables
+
See also: [submodular_optimization], [concave_function]
Up: [submodular_function]
diff --git a/trail b/trail
@@ -0,0 +1,7 @@
+# Trail
+
+A [walk] where [vertices] can repeat, but not [edges]
+
+Up: [path]
+
+See also: [walk], [simple_path]
diff --git a/universality_automata b/universality_automata
@@ -10,6 +10,8 @@ The [computational_problem] of testing if an [automaton] accepts every possible
- [factor_universal]
- [subword_universal]
+Variant: [length_universality_automata]
+
Up: [universality_problem], [automata_problems]
See also: [totality], [validity], [taulology], [automaton_emptiness]
diff --git a/variable b/variable
@@ -0,0 +1,11 @@
+# Variable
+
+Something that stands for a value, in an [equation] or a [logic_formula]
+
+- [free_variable]
+
+Up: [logic]
+
+See also: [constant]
+
+Aliases: variables
diff --git a/walk b/walk
@@ -6,8 +6,8 @@ A [path] where [vertices] and [edges] can freely repeat
- [random_walk]
- [no_meet]
-Up: [graph_basic_notions]
+Up: [path]
-See also: [tree_walking_automaton]
+See also: [tree_walking_automaton], [simple_path]
Aliases: walks
diff --git a/zivny2009expressive b/zivny2009expressive
@@ -0,0 +1,10 @@
+# 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]
