commit 0e7c23954a729dabcc60581f406036f7d22712b2 parent d1382dba00a77e1fbe999663313c31257240cc27 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Thu, 20 Mar 2025 17:23:51 +0100 Merge branch 'master' of a3nm.net:git/wiki_research Diffstat:
49 files changed, 368 insertions(+), 17 deletions(-)
diff --git a/approximation_class b/approximation_class @@ -1,10 +1,10 @@ # Approximation classes -- FPRAS [fpras]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure - - variant QPRAS [qpras] with "quasi-polynomial time" [quasipolynomial] -- PRAS [pras]: same but not polynomial in 1/e -- without R, a deterministic algorithm (PRAS vs PTAS [ptas], FPRAS vs FPTAS [fptas]) -- APX [apx]: there is an approximation algorithm for a certain fixed epsilon +- [FPRAS]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure + - variant [QPRAS] with [quasi-polynomial] time +- [PRAS]: same but not polynomial in 1/e +- without R, a deterministic algorithm ([PRAS] vs [PTAS], [FPRAS] vs [FPTAS]) +- [APX]: there is an [approximation_algorithm] for a certain fixed epsilon Up: [complexity_class] of [approximation] diff --git a/bag_cq_containment b/bag_cq_containment @@ -1,9 +1,11 @@ # Bag cq containment -bag [query_containment] for [CQs] is [open_problem] +[computational_complexity] of [query_containment] for [CQs] under [bag_semantics] is [open_problem] - introduced in [chaudhuri1993optimization] - withdrawn claim of [Pi_2_p]-hardness - only known [lower_bound] is [NP_hard] +Recent discussion: [marcinkowski2025bag] + Up: [containment_bag_semantics], [CQs] diff --git a/bounded_problem b/bounded_problem @@ -0,0 +1,11 @@ +# Bounded problem + +studied in [axelsson2008analyzing] + +- [language_inclusion_bounded] +- [language_equivalence_bounded] +- [language_intersection_bounded] +- [language_universality_bounded] +- [CFG_ambiguity_bounded] + +Up: [formal_language_computational_problem] diff --git a/commutative_closure b/commutative_closure @@ -0,0 +1,9 @@ +# Commutative closure + +The *commutative closure* of a [formal_language] L is the set of all [words] that admit a [permutation] in L + +[commutative_closure_does_not_preserve_regularity]: If L is a [regular_language], then the commutative closure is not necessarily a [regular_language] + +Up: [formal_language_closure_operation] + +See also: [language_commutative] diff --git a/commutative_closure_does_not_preserve_regularity b/commutative_closure_does_not_preserve_regularity @@ -0,0 +1,5 @@ +# Commutative closure does not preserve regularity + +If L is a [regular_language], then the commutative closure is not necessarily a [regular_language]! + +Up: [mathematical_observation] about [commutative_closure] and [regular_languages] diff --git a/context_free_language b/context_free_language @@ -8,4 +8,4 @@ Up: [language], [context_free_grammar] -Aliases: context-free languages, context free languages, context-free language, CFL +Aliases: context-free languages, context free languages, context-free language, CFL, CFLs diff --git a/convexity b/convexity @@ -4,5 +4,6 @@ - [convex_set] - [convex_hull] - [cnf_variable_convex] +- [language_convex] Up: [mathematics] diff --git a/degree b/degree @@ -8,3 +8,5 @@ In [directed_graphs], we can distinguish the [indegree] and [outdegree], respect - [average_degree] Up: [graph_basic_notions] + +See also: [bounded_degree] diff --git a/derivative b/derivative @@ -0,0 +1,11 @@ +# Derivative + +https://en.wikipedia.org/wiki/Brzozowski_derivative + +Given a [word] u and a [formal_language] L, the *derivative* of L by u, written u^{-1} L, is the set of [words] v such that we have uv in L + +We can also define the *derivative* of a [formal_language], cf [quotient_formal_language] + +See also: [variety] + +Up: [formal_language] diff --git a/dynamic_membership_push_pop b/dynamic_membership_push_pop @@ -0,0 +1,5 @@ +# Dynamic membership push pop + +- for [regular_languages]: [guardian_algorithm] in [ganardi2022low] + +Up: [dynamic_membership_word], [push_pop] diff --git a/dynamic_membership_word b/dynamic_membership_word @@ -3,7 +3,8 @@ - [dynamic_membership_regular] - [incremental_maintenance_cfg] -Depends on which [updates_word] are allowed +Depends on which [updates_word] are allowed: +- for [push_pop]: [dynamic_membership_push_pop] [Generalizations]: - [incremental_parsing] diff --git a/factor b/factor @@ -3,6 +3,7 @@ Definition: [word] u is factor of [word] v if we have v = xuy for some [words] x and y - [factor_universal] +- [factorial_language] - [absent_factor] If u is a factor of v, then v is an [extension] of u diff --git a/finite_simple_group b/finite_simple_group @@ -0,0 +1,9 @@ +# Finite simple group + +A finite [group] is simple if it does not have non-trivial [normal_subgroups] + +[classification_of_finite_simple_groups] + +Up: [group], [finite] + +Aliases: finite simple groups diff --git a/formal_language_closure_operation b/formal_language_closure_operation @@ -0,0 +1,11 @@ +# Formal language closure operation + +Specific case: [regular_language_closure_operation] + +- [upwards_closure] +- [downwards_closure] +- [commutative_closure] + +Up: [closure_operation], [formal_language] + +See also: [formal_language_operator] diff --git a/formal_language_computational_problems b/formal_language_computational_problems @@ -3,6 +3,7 @@ - [membership_problem] - [language_inclusion] - [language_equivalence] +- [bounded_problem] Up: [formal_language] diff --git a/formal_language_mirror b/formal_language_mirror @@ -0,0 +1,9 @@ +# Formal language mirror + +The mirror of a [formal_language] L is the language formed of the [mirrors] of the [words] of L + +Up: [formal_language_operator] + +Aliases: language mirror, mirror language + +See also: [commutative_closure] diff --git a/formal_language_operator b/formal_language_operator @@ -0,0 +1,22 @@ +# Formal language operator + +An [operator] that takes one or two [formal_languages] and creates a new [formal_language] + +- [boolean_operators] + - [language_union] + - [language_intersection] + - [language_complementation] +- [concatenation] +- [kleene_star] +- [morphism] / [inverse_morphism] +- [quotient_formal_language] + - see [derivative] +- [wreath_product] +- [semidirect_product] +- [shuffle] +- [formal_language_mirror] +- [formal_language_closure_operation]: an operator that takes one [formal_language] and extends it by adding more [words] to it + - [upward_closure] / [downward_closure] + - [commutative_closure] + +Up: [formal_language], [operator] diff --git a/graph_operations b/graph_operations @@ -4,5 +4,6 @@ - [graph_product] - [edge_contraction] - [underlying_undirected_graph] +- [subdivision] Up: [graph] diff --git a/group b/group @@ -0,0 +1,23 @@ +# Group + +A *group* is an [algebraic_structure] which is like a [monoid] but additionally requires that each [element] has an [inverse] + +Types of groups: + +- [coxeter_groups] +- [solvable_group] +- [group_abelian] + +[Theorems]: + +- classification of [finite_simple_groups] +- [feit_thompson] theorem + +Tools: + +- [cayley_graph] +- [cayley_table] + +Up: [algebraic_structure], [mathematics] + +See also: [monoid], [group_language] diff --git a/group_abelian b/group_abelian @@ -1,5 +1,9 @@ # Group abelian -[commutative] +A [group] which is [commutative] -Up: [group] +Up: [group], [commutative] + +Aliases: abelian group, abelian groups + +See also: [language_commutative], [semiring_commutative] diff --git a/guardian_algorithm b/guardian_algorithm @@ -0,0 +1,7 @@ +# Guardian algorithm + +https://cstheory.stackexchange.com/questions/45890/constraints-on-sliding-windows/46762 + +[ganardi2022low] + +Up: [algorithm] for [dynamic_membership_push_pop] diff --git a/language_commutative b/language_commutative @@ -0,0 +1,9 @@ +# Commutative language + +- [regular_language_commutative] + +Up: [formal_language] which is [commutative] + +See also: [parikh_image], [Commutative_closure] + +Aliases: commutative language, commutative languages diff --git a/language_complementation b/language_complementation @@ -0,0 +1,7 @@ +# Language complementation + +The [complementation] of a [formal_language] + +Up: [complementation] + +Aliases: language complement diff --git a/language_downwards_closed b/language_downwards_closed @@ -0,0 +1,20 @@ +# Language downwards closed + +A [formal_language] is *downwards closed* if any [subword] of the [formal_language] is in the [formal_language] + +[ideal_decomposition]: every downward closed language is a finite [union] of [language_ideal] i.e. terms of the form + + A_1^* {a_1, epsilon} ... A_k^* + where the A_i are subalphabets + +[language_downwards_closed_details] + +The [language_complement] of a downwards closed [formal_language] is a [upwards_closed_language]. + +Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite] + +Up: [regular_language_family] + +See also: [higmans_lemma], [downwards_closure], [language_factor_minimal], [language_upwards_closed], [ganardi2024directed] + +Aliases: downward closed language, downward closed languages, downwards closed language, downwards closed languages diff --git a/language_inclusion b/language_inclusion @@ -1,6 +1,7 @@ # Language inclusion - [pattern_language_inclusion] +- [language_inclusion_bounded] Up: [formal_language_computational_problems], [inclusion] diff --git a/language_inclusion_bounded b/language_inclusion_bounded @@ -0,0 +1,9 @@ +# Language inclusion bounded + +Given two [formal_languages] L_1 and L_2, and a length k, is it true that L_1 cap Sigma^{\leq k} is included in L2 cap Sigma^{\leq k}? + +studied in [axelsson2008analyzing] + +Up: [language_inclusion], [bounded_problem] + +Aliases: bounded language inclusion diff --git a/lmim_width b/lmim_width @@ -0,0 +1,9 @@ +# LMIM width + +This is to [mim_width] like [pathwidth] is to [treewidth] + +cf [golovach2017output] + +Can be computed on [trees] in [log_linear] time, cf [hogemo2019linear] + +Up: [mim_width], [width_measure_linear] diff --git a/locally_threshold_testable_language b/locally_threshold_testable_language @@ -0,0 +1,16 @@ +# Locally_threshold_testable_language + +Discussed in [bojanczyk2007new] + +A [formal_language] is *locally threshold testable* if it is a [Boolean_combination] of [formal_languages] of the form: +- words having a given [word] w as a [prefix] +- words having a given [word] w as a [suffix] +- words having a given [word] w as a [factor] at least n times + +Generalizes [locally_testable_languages] + +Up: [locally_testable_language] + +See also: [local_language] + +Aliases: LTT language, LTT diff --git a/maximum_linear_arrangement b/maximum_linear_arrangement @@ -0,0 +1,7 @@ +# Maximum linear arrangement + +cf [alemanypuig2024maximum] + +See also: [minimum_linear_arrangement] + +Up: [computational_problem] on [graph] diff --git a/mim_width b/mim_width @@ -4,7 +4,7 @@ defined in [vatshelle2012new] via [induced_matching] -linear version [lmim_width], like [pathwidth] is to [treewidth], cf [golovach2017output] +[width_measure_linear]: [lmim_width] variant [sim_width] diff --git a/minimization b/minimization @@ -5,3 +5,7 @@ - [automaton_minimal] Up: [theoretical_computer_science] + +Aliases: minimized + +See also: [minimum], [maximization] diff --git a/minimum b/minimum @@ -7,6 +7,6 @@ The smallest element of an [order] Up: [mathematics_basic_concepts] -See also: [maximum] +See also: [maximum], [minimization] Aliases: min diff --git a/minimum_linear_arrangement b/minimum_linear_arrangement @@ -0,0 +1,11 @@ +# Minimum linear arrangement + +Given a [graph], find a [permutation] of the [vertices] such that the [sum] across [edges] of the difference between the permutation image of the two endpoint [vertices] is [minimized] + +The problem is [NP_complete] + +cf [bienkowski2024improved] + +Up: [computational_problem] on [graph] + +See also: [graph_layout], [maximum_linear_arrangement] diff --git a/minimum_unsatisfiable_core b/minimum_unsatisfiable_core @@ -0,0 +1,11 @@ +# Minimum unsatisfiable core + +A subset of the [clauses] of a [CNF] [Boolean_formula] which is [unsatisfiable] and has a [minimum] number of clauses + +It is [sigmap2]_complete to compute +- https://cstheory.stackexchange.com/questions/54692/complexity-of-computing-minimum-unsatisfiable-core +[umans1999hardness] + +cf also [gupta2006learning] + +Up: [minimal_unsatisfiable] diff --git a/mirror b/mirror @@ -0,0 +1,9 @@ +# Mirror + +Given a [word] w = a_1 ... a_n, its mirror is w' = a_n ... a_1 + +Up: [word] + +See also: [automata_reversal], [palindrome], [commutative_closure] + +Aliases: mirrors diff --git a/normal_subgroup b/normal_subgroup @@ -9,3 +9,5 @@ Can be used to build [quotient_group] by a [congruence_relation]: the equivalenc When the group is [abelian_group], all subgroups are normal Up: [finite_simple_group] + +Aliases: normal subgroups diff --git a/packing_coloring b/packing_coloring @@ -0,0 +1,9 @@ +# Packing coloring + +work with [bernardo] + +https://www.quantamagazine.org/the-number-15-describes-the-secret-limit-of-an-infinite-grid-20230420/ + +Up: [mathematics] + +See also: [graph_coloring], [packing_problem] diff --git a/parikh_image b/parikh_image @@ -0,0 +1,16 @@ +# Parikh image + +The *Parikh image* of a [word] is the [vector] of the number of occurrences of the letters that it contains, and the *Parikh image* of a [formal_language] is the set of Parikh images of the [words] that it contains + +[Parikhs_theorem]: the Parikh images of [CFLs] and of [regular_languages] are the same! + +The Parikh image is not always [recognizable] even for a [regular_language] +- https://cstheory.stackexchange.com/questions/46670/languages-whose-parikh-image-is-recognizable +- it relates to [regular_languages] whose [commutative_closure] is also a [regular_language] + - cf [commutative_closure_does_not_preserve_regularity] + +Up: [formal_language_theory] + +See also: [language_commutative], [length] + +Aliases: parikh images diff --git a/pathwidth b/pathwidth @@ -3,7 +3,8 @@ like [treewidth] but for [tree_decomposition] which is a [path] - [pathwidth_directed] -- [pathwidth_approximation] +- [pathwidth_computation] + - [pathwidth_approximation] Up: [width_measure], [path] diff --git a/pathwidth_computation b/pathwidth_computation @@ -0,0 +1,12 @@ +# Pathwidth computation + +The [computational_problem] of computing the [pathwidth] of an input [graph] + +https://en.wikipedia.org/wiki/Pathwidth#Special_classes_of_graphs +- Is [NP_complete] even on [bounded_degree] [planar_graphs] +- Can be computed in [linear_time] for [trees] and [forests] +- Can be computed in [polynomial_time] for [treelike] [graphs] + +- [pathwidth_approximation] + +Up: [computational_problem], [pathwidth] diff --git a/pathwidth_directed b/pathwidth_directed @@ -9,3 +9,5 @@ Relationship to [pathwidth]: Up: [pathwidth] See also: [treewidth_directed] + +Aliases: directed pathwidth diff --git a/pop_operation b/pop_operation @@ -0,0 +1,9 @@ +# Pop operation + +Given a non-empty [word] w and a side (left or right), remove the endpoint [letter] + +See also: [push_operation] + +Aliases: pop operations + +Up: [deletion] diff --git a/push_operation b/push_operation @@ -0,0 +1,9 @@ +# Push operation + +Given a [word] w and a [letter] a and one side of the word (left or right), add a to that side of the word + +Up: [insertion] + +See also: [pop_operation] + +Aliases: push operations diff --git a/push_pop b/push_pop @@ -0,0 +1,9 @@ +# Push pop + +The kinds of [updates_word] where you can do [push_operations] and [pop_operations] + +- [dynamic_membership_push_pop] + +For [dynamic_membership] + +Up: [update_word] diff --git a/shuffle b/shuffle @@ -1,6 +1,9 @@ # Shuffle +A [word] w is a *shuffle* of two [words] u and v if we can interleave the characters of u and v to form w. We can also define the *shuffle* of two [formal_languages] L and L' as the set of [words] w that are shuffles of a [word] of L and a [word] of L' + - [shuffle_square] -- a finite set of [word] can be decomposed into at most one multiset of which it is the shuffle: see [berstel2002shuffle] +- a finite set of [words] can be decomposed into at most one multiset of which it is the shuffle: + - see [berstel2002shuffle] -Up: [formal_language_theory] +Up: [formal_language_operator] diff --git a/subdivision b/subdivision @@ -0,0 +1,9 @@ +# Subdivision + +In a [graph], given an [edge], replace this [edge] by a [path] whose intermediate [vertices] are fresh + +Up: [graph_operations] + +See also: [edge_contraction], [topological_minor] + +Aliases: subdivisions diff --git a/submodular_maximization b/submodular_maximization @@ -1,8 +1,8 @@ # Submodular maximization -[np_hard] +An [NP_hard] [computational_problem] -[buchbinder2024deterministic] +cf [buchbinder2024deterministic] Up: [submodular_optimization], [maximization] diff --git a/upwards_closure b/upwards_closure @@ -0,0 +1,16 @@ +# Upwards closure + +For L a [formal_language], the *upwards closure* of L is the set of [words] w which are [supersequences] of a word of L + +For any [formal_language] L, the upwards closure is a [regular_language]: this uses [Higman's_lemma] + +The upwards closure is a [upwards_closed_language]: any [supersequence] of a [word] of the upwards closure is in the upwards closure + +- [upwards_closure_state_complexity] + - [upwards_closure_cfl_state_complexity] + +See also: [language_upwards_closed], [downwards_closure] + +Up: [formal_language_operator], [closure_operation] on [supersequences] + +Aliases: upward closure, superword closure diff --git a/width_measure_linear b/width_measure_linear @@ -0,0 +1,6 @@ +# Width measure linear + +- [pathwidth] +- [lmim_width] + +Up: [width_measure]