commit bc94ae7b86bfd7f7a01ab694b8c91bdc01e15566 parent e224a3a1c5ecd2b6fb85d40d06aa169084a0df9d Author: Antoine Amarilli <a3nm@a3nm.net> Date: Mon, 2 Jun 2025 23:05:25 +0200 commit with codex Diffstat:
50 files changed, 391 insertions(+), 19 deletions(-)
diff --git a/2horn b/2horn @@ -0,0 +1,11 @@ +# 2horn + +A [conjunction] of [2horn_clauses] + +- [horn_2sat] + +Up: [Boolean_function] + +Aliases: 2 horn + +See also: [3horn] diff --git a/abokhamis2024fast b/abokhamis2024fast @@ -0,0 +1,9 @@ +# Abokhamis2024fast + +[academic_paper] by [mahmoud] and [dan_suciu] and [xiao_hu] + +- concerns [boolean_CQs] specifically (all variables projected away) +- defines [omega_submodular_width] to unify [submodular_width] with [boolean_matrix_multiplication] +- connections with [information_theory] + +Up: [academic_paper] on [conjunctive_query_matrix_multiplication] diff --git a/automata_generalized b/automata_generalized @@ -0,0 +1,13 @@ +# Generalized automata + +[automata] where transitions are labeled by strings rather than letters + +introduced in [eilenberg1974automata] + +The [computational_problem] of determining the minimum number of states of a generalized [automata_nondeterministic] that recognizes a given [regular_language] is [decidable] [hashiguchi1991algorithms] + +notion of [automata_deterministic] for this formalism: [giammarresi1995deterministic] + +no notion of [minimization], but [cotumaccio2024myhill] proposes a notion to make it work + +Up: [automata] diff --git a/automata_unary b/automata_unary @@ -1,15 +0,0 @@ -# Automata unary - -#TODO universality complexity? - -[Automata] on [alphabet_unary] - -- for [DFAs]: [ultimately_periodic] -- for [UFAs]: [automata_unary_ufa] -- for [NFAs]: - - [chrobak_normal_form] - - [nfa_unary_lengths] - -Up: [automata_classes] - -See also: [tortoise_and_hare_algorithm], [language_unary] diff --git a/automatic_graph b/automatic_graph @@ -0,0 +1,7 @@ +# Automatic graph + +A [directed_graph] on the set of all [words] where the edge relation is an [automatic_relation] + +See also: [barcelo2023separating], [automatic_structure] + +Up: [graph], [automatic_relation] diff --git a/axiom b/axiom @@ -0,0 +1,7 @@ +# Axiom + +The initial [nonterminal] of a [context_free_grammar] + +Up: [context_free_grammar] + +See also: [initial_state] diff --git a/chinese_postman_problem b/chinese_postman_problem @@ -0,0 +1,14 @@ +# Chinese postman problem + +The [computational_problem] of computing the shortest [path] or [circuit] that visits every [edge] of a [graph] at least once + +Can be posed for [graph_directed] or [graph_undirected] + +[NP_complete] on: +- [Undirected_graphs] when traversal cost is different per direction: [windy_postman_problem] +- on [mixed_graphs]: [mixed_chinese_postman_problem] +- if only a subset of the edges are required + +See also: [eulerian_path], [traveling_salesperson_problem] + +Up: [computational_problem] on [graph] diff --git a/chordal b/chordal @@ -10,3 +10,5 @@ Equivalently, an [undirected_graph] is chordal iff it has a [perfect_elimination See also: [hypergraph_chordal], [proper_chordal_graph] Up: [graph] + +Aliases: chordal graph, chordal graphs diff --git a/cnf_to_dnnf b/cnf_to_dnnf @@ -0,0 +1,10 @@ +# CNF to DNNF + +[Conversion] of a [CNF] to a [DNNF] + +[bova2015compiling]: +- [fixed_parameter_tractable] bound in [incidence_treewidth] +- linear in [variable] plus [clauses] +- gives a [structured_ddnnf] + +Up: [conversion] of [conjunctive_normal_form] to [dnnf] diff --git a/complexity_hierarchy b/complexity_hierarchy @@ -0,0 +1,8 @@ +# Complexity hierarchy + +- [polynomial_hierarchy] +- [boolean_hierarchy] + +Up: [hierarchy] of [complexity_class] + +See also: [time_hierarchy_theorem], [space_hierarchy_theorem] diff --git a/context_free_grammar_polyslender b/context_free_grammar_polyslender @@ -0,0 +1,9 @@ +# Context free grammar polyslender + +[CFG] recognizing a [formal_language] which is [polyslender] + +[illie2000characterization]: a [context_free_language] is [polyslender] iff it is [bounded] + +Up: [context_free_grammar], [polyslender] + +See also: [context_free_language_polyslender] diff --git a/counter_automata_one b/counter_automata_one @@ -0,0 +1,14 @@ +# One-counter automata (OCA) + +Related concept: [one_counter_nets] + +Generalization: [counter_automata_trees] + +- [counter_automata_one_deterministic] + +[conversion] of OCA to [DFA] requires doubly exponential number of [states] + - e.g., "the n-th character from the end is an a", with n coded in binary + +Up: [counter_automata] + +See also: [counter_automata_two], [vector_addition_system] diff --git a/crpq_containment b/crpq_containment @@ -0,0 +1,7 @@ +# CRPQ containment + +[EXPSPACE_complete]: cf [calvanese2000containment] + +[beaudou2023complexity] + +Up: [crpq], [query_containment] diff --git a/equality_generating_dependency b/equality_generating_dependency @@ -0,0 +1,9 @@ +# Equality generating dependency (EGDs) + +A [database_dependency] in which the head is an [equality] [atom] + +- [functional_dependency] + +Up: [database_dependency], [first_order_logic] + +Aliases: EGD, EGDs diff --git a/equivalence_automata_pushdown_deterministic b/equivalence_automata_pushdown_deterministic @@ -0,0 +1,9 @@ +# Equivalence automata pushdown deterministic + +Was shown [decidable] by [senizergues1997equivalence] + +Is in [TOWER], cf [jancar2014equivalences] + +Up: [pushdown_automaton_deterministic], [automaton_equivalence] + +Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic diff --git a/eulerian_cycle b/eulerian_cycle @@ -0,0 +1,5 @@ +# Eulerian cycle + +An [Eulerian_path] which is a [cycle], i.e., starts and ends at the same [vertex] + +Up: [eulerian_path] diff --git a/eulerian_path b/eulerian_path @@ -0,0 +1,13 @@ +# Eulerian path + +A [path] that visits every [edge] of a [graph] exactly once + +Can be defined for [graph_directed] or [graph_undirected] + +[Decision_problem]: [Eulerian_path_decision] + +Variants: +- [eulerian_cycle] +- [chinese_postman_problem] + +Up: [path] diff --git a/eulerian_path_decision b/eulerian_path_decision @@ -0,0 +1,13 @@ +# Eulerian path decision + +The [computational_problem] of deciding whether a [graph] admits a [eulerian_path] + +It is in [PTIME] on [directed_graphs] and [undirected_graphs] + +Further, for [Eulerian_circuits], the following is true: +- a [directed_graph] admits a [Eulerian_circuit] if and only if it is [strongly_connected] and for each [vertex] the [indegree] is equal to the [outdegree] + - for such graphs being [strongly_connected] or [weakly_connected] is [equivalent] + +Up: [computational_problem], [eulerian_path] + +See also: [chinese_postman_problem] diff --git a/first_order_sentence b/first_order_sentence @@ -0,0 +1,7 @@ +# First order sentence + +A [first_order_logic] [logic_formula] which is a [sentence] + +Up: [first_order_logic], [sentence] + +Aliases: FO sentence, FO sentences diff --git a/friendship_graph b/friendship_graph @@ -0,0 +1,7 @@ +# Friendship graph + +A [graph_undirected] consisting of several [triangles] glued on one [universal_vertex] + +Up: [graph_family] + +See also: [friendship_theorem] diff --git a/ganian2022weighted b/ganian2022weighted @@ -0,0 +1,5 @@ +# Ganian2022weighted + +https://arxiv.org/abs/2206.01706 + +Up: [academic_paper] on [twin_width] diff --git a/graph_bridgeless b/graph_bridgeless @@ -0,0 +1,7 @@ +# Graph bridgeless + +A [graph] without a [bridge] + +See also: [biconnected_component] + +Up: [graph] diff --git a/graph_mixed b/graph_mixed @@ -5,3 +5,5 @@ A [graph] featuring both [directed_edges] and [undirected_edges] Up: [graph] See also: [graph_directed], [graph_undirected] + +Aliases: mixed graph, mixed graphs diff --git a/hu2024output b/hu2024output @@ -0,0 +1,10 @@ +# Hu2024output + +[Academic_paper] on the complexity of [yannakakis_algorithm] + +- for queries over [semiring], shows a kind of optimality +- better bound for [join_aggregate] [acyclic_queries] + +Up: [academic_paper] by [xiao_hu] + +See also: [hu2024fast] diff --git a/incremental_maintenance_mso b/incremental_maintenance_mso @@ -0,0 +1,6 @@ +# Incremental maintenance MSO + +- [balmin2004incremental] +- more recent results via [enumeration]: [incremental_maintenance_enumeration_mso] + +Up: [query_evaluation_incremental], [monadic_second_order_logic] diff --git a/independent_set_enumeration b/independent_set_enumeration @@ -0,0 +1,5 @@ +# Independent set enumeration + +[kurita2021constant] + +Up: [enumeration], [independent_set] diff --git a/language_polyslender b/language_polyslender @@ -0,0 +1,9 @@ +# Language polyslender + +[Formal_language] whose [density_function] is [upper_bounded] by a [polynomial] + +- [context_free_grammar_polyslender] + +Up: [formal_language], [density_function] + +See also: [language_slender], [bounded_language] diff --git a/longest_common_extension b/longest_common_extension @@ -0,0 +1,9 @@ +# Longest common extension + +Uses [suffix_array] + +Related open problem: [mirror_lce] + +Up: [stringology] + +See also: [longest_common_subsequence] diff --git a/los_tarski_theorem b/los_tarski_theorem @@ -0,0 +1,11 @@ +# Los-Tarski theorem + +A [first_order_sentence] φ is [preserved_under_extensions] iff φ is [logic_equivalent] to an [existential_first_order] [first_order_sentence] + +Cf [lopez2021preservation] + +Does not [relativize] to [finite_models], cf [counterexample] in [tait1959counterexample] + +Up: [theorem] + +Aliases: Los_Tarski diff --git a/ltl b/ltl @@ -0,0 +1,5 @@ +# LTL + +Has same expressive power as [FO] on [words] + +Up: [logic] diff --git a/maximal_independent_set b/maximal_independent_set @@ -0,0 +1,7 @@ +# Maximal independent set + +- [maximal_independent_set_counting] + +Up: [independent_set] + +See also: [maximum_independent_set] diff --git a/maximal_independent_set_counting b/maximal_independent_set_counting @@ -1,7 +1,9 @@ # Maximal independent set counting -tractable for [cograph] (P4-free [graph]) -- cf [corneil1981complement] -- mentioned in [livshits2021counting] +- tractable for [cographs] + - cf [corneil1981complement] + - mentioned in [livshits2021counting] +- [sharpp_hard] even on [chordal_graphs]: + - [okamoto2008counting] Up: [counting_problem], [maximal_independent_set] diff --git a/monotone b/monotone @@ -0,0 +1,7 @@ +# Monotone + +Something that grows when the input grows + +Up: [mathematics] + +See also: [homomorphism_closed], [positive_vs_monotone], [positive], [Preserved_under_extensions] diff --git a/monotone_two_variable_per_inequality b/monotone_two_variable_per_inequality @@ -0,0 +1,7 @@ +# Monotone two variable per inequality + +[TVPI] with constraints of the form ax + by <= d with a and b of different [signs] + +Intractable according to [devlas2024complexity] + +Up: [two_variable_per_inequality] diff --git a/nfa_acceptance_hypothesis b/nfa_acceptance_hypothesis @@ -0,0 +1,7 @@ +# NFA acceptance hypothesis + +Hypothesis 2 in [bringmann2024nfa] + +Implies [OMV_hypothesis] + +Up: [bringmann2024nfa], [computational_hypothesis] diff --git a/nfa_unary_lengths b/nfa_unary_lengths @@ -0,0 +1,12 @@ +# NFA unary lengths + +An [NFA] which is [automata_unary], i.e., on a [unary_alphabet] + +- testing acceptance: [potechin2020regular] + - [lower_bound] from [triangle_detection] + - already for [automata_acyclic] + - also [lower_bound] from [orthogonal_vectors] +- listing accepted lengths: [potechin2020regular] +- generalizes [subset_sum] with inputs coded in unary + +Up: [automata_unary], [nfa_acceptance] diff --git a/positive_vs_monotone b/positive_vs_monotone @@ -0,0 +1,7 @@ +# Positive vs monotone + +- [positive] "positive" means "no negations" (syntactic) +- [monotone] "monotone" means "expresses a [monotone] function", i.e., equivalent to a positive circuit (semantic) + - but a monotone [circuit] can sometimes be made much more concise via the use of [negation] + +Up: [circuit] diff --git a/preserved_under_extensions b/preserved_under_extensions @@ -0,0 +1,7 @@ +# Preserved under extensions + +A [formula] φ is *preserved under [extensions]* if the following is true: if an [instance] I satisfies φ and I is an [induced_subinstance] of J then J satisfies φ + +Up: [logic] + +See also: [monotone] diff --git a/qpoly b/qpoly @@ -0,0 +1,8 @@ +# Qpoly + +[computational_problem] of solving an [equation] involving a [quadratic_polynomial]: given a, b, c in [binary_encoding], determine if there exist [natural_numbers] x and y such that a x^2 + b y = c + +- shown [np_hard] in [manders1976np] +- used in [boeker2024complexity] + +Up: [computational_problem] diff --git a/rpq_output_sensitive b/rpq_output_sensitive @@ -0,0 +1,5 @@ +# Rpq output sensitive + +[abokhamis2024output]: improves on [product_graph] by doing an [output_sensitive_algorithm] + +Up: [rpq_query_evaluation] diff --git a/satisfiability_weighted_ddnnf_negation b/satisfiability_weighted_ddnnf_negation @@ -0,0 +1,11 @@ +# Satisfiability weighted ddnnf negation + +The [computational_problem] of deciding whether a [dDNNF] has a [falsifying_assigment] of a given weight? + +Already challenging for [orthogonal_DNF], cf [satisfiability_weighted_orthogonal_DNF_negation] + +But tractable when weights are written in [unary] + +Related to [ddnnf_complementation] + +Up: [satisfiability_weighted_knowledge_compilation], [ddnnf], [ddnnf_complementation] diff --git a/stationary_distribution b/stationary_distribution @@ -0,0 +1,7 @@ +# Stationary distribution + +A [distribution] \pi on [markov_chain] P is stationary if \pi = \pi P. + +- also a left-[eigenvector] of [eigenvalue] 1 + +Up: [markov_chain] diff --git a/suffix_array b/suffix_array @@ -0,0 +1,9 @@ +# Suffix array + +can be used for [pattern_matching], because the occurrences of a pattern form a contiguous sequence of the suffix array + +can be used for [longest_common_extension], when adding an [lcp_table] + +Up: [stringology], [data_structure] + +See also: [suffix_tree] diff --git a/symmetry b/symmetry @@ -0,0 +1,9 @@ +# Symmetry + +- [symmetric_encryption] +- [symmetric_automata] +- [datalog_symmetric_linear] +- [relation_symmetric] +- [symmetric_model_counting] + +Up: [mathematics] diff --git a/tree_evaluation_problem b/tree_evaluation_problem @@ -0,0 +1,9 @@ +# Tree evaluation problem + +You have a [tree] and you want to evaluate a [bottom_up_nondeterministic_tree_automaton] on the tree, in a [nonuniform] sense where each [node] is labeled by the transition function + +It is in O(log n log log n), cf [cook2023tree] + +Up: [computational_problem] on [tree] + +Aliases: TreeEval diff --git a/tree_traversal b/tree_traversal @@ -0,0 +1,9 @@ +# Tree traversal + +- [prefix_traversal] +- [infix_traversal] +- [postfix_traversal] + +Up: [tree] + +See also: [top_down], [bottom_up] diff --git a/universal_vertex b/universal_vertex @@ -0,0 +1,5 @@ +# Universal vertex + +A *universal vertex* in an [undirected_graph] is a [vertex] which is [adjacent] to every other [vertex] + +Up: [graph_theory] diff --git a/universality_automata b/universality_automata @@ -1,6 +1,6 @@ # Universality automata -[computational_problem]: test if [automata] accepts every possible [word] +The [computational_problem] of testing if an [automaton] accepts every possible [word] - [universality_automata_nondeterministic]: [conp_complete] - [universality_automata_deterministic]: [ptime] @@ -13,3 +13,5 @@ Up: [universality_problem], [automata_problems] See also: [totality], [validity], [taulology], [automaton_emptiness] + +Aliases: automata universality, automaton universality diff --git a/universality_context_free_grammar b/universality_context_free_grammar @@ -0,0 +1,7 @@ +# Universality context free grammar + +[universality_problem] for [CFGs]: it is [undecidable] + +Up: [universality_problem] + +See also: [universality_automata] diff --git a/weighted_mso b/weighted_mso @@ -0,0 +1,7 @@ +# Weighted MSO + +- [automata_weighted] + +See also: [quantitative_mso], [counting_mso], [weighted_language] + +Up: [monadic_second_order], [weighted_logic]