commit 9338f1833b2e0fd51ac22d5f7a98e998a90859be parent 79cded9485de1805dfefc80a493fb6869e2bc246 Author: Antoine Amarilli <a3nm@a3nm.net> Date: Mon, 19 Jan 2026 22:15:24 +0100 Merge remote-tracking branch 'origin/master' Diffstat:
54 files changed, 293 insertions(+), 32 deletions(-)
diff --git a/algorithm_randomized b/algorithm_randomized @@ -16,4 +16,4 @@ Up: [algorithms] See also: [fpras], [rp], [complexity_random], [randomness], [derandomization], [randomized_reduction] -Aliases: randomized +Aliases: randomized, randomized algorithm, randomized algorithms diff --git a/approximate_pattern_matching b/approximate_pattern_matching @@ -1,10 +1,16 @@ # Approximate pattern matching -- find all occurrences of a pattern P in text T up to k modifications ([edit_distance]) +- find all occurrences of a pattern P in text T up to k modifications ([string_distance]) - only report the end of matches to avoid quadratic output +can be for [hamming_distance] or for [edit_distance] (cf [navarro2001guided]) + variant: [approximate_pattern_matching_streaming] +special cases when the [string_distance] is not too big (bounded by k): +- [k_mismatch_pattern_matching] for [hamming_distance] +- [k_edit_pattern_matching] for [edit_distance] + [academic_papers]: - [hazay2007approximate] diff --git a/arithmetic b/arithmetic @@ -9,6 +9,7 @@ - [modulo] - [GCD] - [coprime] +- [chinese_remainder_theorem] Up: [mathematics] diff --git a/cfl_commutative_closure_regular b/cfl_commutative_closure_regular @@ -0,0 +1,8 @@ +# CFL commutative closure regular + +The [CFLs] whose [commutative_closure] is [regular_language] +- cf https://cstheory.stackexchange.com/a/48457 + +See also: [parikhs_theorem], [commutative_closure_does_not_preserve_regularity], [commutatively_regular] + +Up: [CFL] diff --git a/commutatively_equivalent b/commutatively_equivalent @@ -0,0 +1,5 @@ +# Commutatively equivalent + +In [carpi2021commutative]: two languages are *commutatively equivalent* if there is a [bijection] between them which preserves the [parikh_image] + +Up: [commutatively_regular] diff --git a/commutatively_regular b/commutatively_regular @@ -0,0 +1,9 @@ +# Commutatively regular + +In [carpi2021commutative]: a [formal_language] is *commutatively regular* if it is [commutatively_equivalent] to a [regular_language] + +Not straightforward to understand already for [CFLs], cf [carpi2021commutative] + +See also: [cfl_commutative_closure_regular] + +Up: [formal_language] diff --git a/context_free_grammar b/context_free_grammar @@ -9,6 +9,7 @@ - [derivation_tree] - [context_free_language] - [proto_word] +- [derivation] ## Equivalence @@ -20,8 +21,11 @@ - [context_free_grammar_deterministic] - [context_free_grammar_unambiguous] - [context_free_grammar_ambiguous] -- [context_free_grammar_ultralinear] - - [context_free_grammar_linear] +- [context_free_grammar_linear] + - [context_free_grammar_ultralinear] + - [context_free_grammar_metalinear] + - [context_free_grammar_superlinear] + - [context_free_grammar_finite_index] - [context_free_grammar_bounded] - [context_free_grammar_polyslender] - [context_free_grammar_finite] diff --git a/context_free_grammar_equivalence_problem b/context_free_grammar_equivalence_problem @@ -5,5 +5,8 @@ The *context free grammar equivalence problem* is the [decision_problem] of test It is [undecidable] on [CFGs], by reduction from [CFG_universality]. It is already [undecidable] on [linear_CFGs], cf [linear_CFG_equivalence] - for [uCFGs] (or with multiplicity of [parse_trees]): [context_free_grammar_unambiguous_equivalence_problem] +- [DPDA_equivalence_problem] Up: [formal_language_computational_problem], [context_free_grammar_equivalence] + +Aliases: CFG equivalence problem, CFG equivalence diff --git a/context_free_grammar_finite_index b/context_free_grammar_finite_index @@ -0,0 +1,24 @@ +# Finite index CFG + +Defined in [salomaa1973formal] Chapter VI section 10: A [CFG] G having a bound k such that every word in the [language_accepted_by] G has a [derivation] with [derivation_index] at most k + +Equivalent characterization: +- non-expansive CFGs*, i.e., those where you cannot rewrite a nonterminal into + multiple copies of itself +- closing the CFLs under substitution, where closing a family under + substitution means closing under the operation where you replace each letter + by a language of the family (cf [salomaa1973formal]): these are called the + "quasi-rational languages" ([autebert1997context], [shemetova2024rational]) + +Strictly generalizes: +- [ultralinear_CFGs] +- [superlinear_CFGs] + +Variant: +- [derivation_bounded_set], i.e., for a [CFG], the sublanguage of [derivation_trees] of bounded [derivation_tree_index] + - defined in [ginsburg1968derivation] + - also discussed in [esparza2016brief] in connection with [Strahler_number] + +Up: [context_free_grammar] + +Aliases: finite index CFG, finite index CFGs, quasirational, quasirational language, non-expansive CFG, non expansive CFG diff --git a/context_free_grammar_metalinear b/context_free_grammar_metalinear @@ -0,0 +1,7 @@ +# Context free grammar metalinear + +Defined in [salomaa1973formal]: a [CFG] is *metalinear* if its axiom rewrites in at most k [nonterminals] that are themselves linear + +Up: [context_free_grammar] + +Aliases: metalinear CFG, metalinear CFGs diff --git a/context_free_grammar_superlinear b/context_free_grammar_superlinear @@ -0,0 +1,16 @@ +# Superlinear CFG + +A CFG where the only allowed nonlinear derivations are of the form X -> YZ +where Z is a linear nonterminal + +Cf [kutrib2007finite] + +Special case: +- [metalinear_CFGs] + +Generalization: +- [finite_index_CFGs] + +Up: [context_free_grammar] + +Aliases: superlinear CFG, superlinear CFGs diff --git a/context_free_grammar_ultralinear b/context_free_grammar_ultralinear @@ -1,9 +1,18 @@ -# Context free grammar ultralinear +# Ultralinear CFG -A [CFG] where there is a bound on the maximal number of [nonterminals] that can occur in any [derivation] +A [CFG] where there is a bound on the maximal number of [nonterminals] that can occur in any [derivation], i.e., where the [derivation_index] of all [derivations] is bounded Can be seen in terms of [PDAs] via the notion of [PDA_finite_turn], studied in [ginsburg1966finite] -Special case: [linear_CFGs] +Special cases: +- [linear_CFGs] +- [metalinear_CFGs] + +Generalization: +- [finite_index_CFGs] Up: [context_free_grammar] + +See also: [context_free_grammar_finite_index], [context_free_grammar_metalinear] + +Aliases: ultralinear CFG, ultralinear CFGs diff --git a/context_free_grammar_unambiguous_equivalence_problem b/context_free_grammar_unambiguous_equivalence_problem @@ -8,4 +8,6 @@ By contrast [language_inclusion] is [undecidable] because [DPDA_inclusion] is [u Up: [context_free_grammar_equivalence_problem], [uCFGs] -Aliases: unambiguous CFG equivalence problem, equivalence context free grammar unambiguous +Aliases: unambiguous CFG equivalence problem, equivalence context free grammar unambiguous, UCFG equivalence, UCFG equivalence problem + +See also: [DPDA_equivalence] diff --git a/cut_and_paste_updates b/cut_and_paste_updates @@ -0,0 +1,6 @@ +# Cut and paste updates + +- [split_update] +- [concatenation_update] + +Up: [update_word] diff --git a/datalog_negation b/datalog_negation @@ -7,6 +7,10 @@ Simple solution: [negation_stratified], i.e., adding [negation] only to [datalog Recent work on this: [shaikhha2024optimizing] +[datalog_negation_provenance] + See also: [fixpoint] -Up: [datalog], [negation] +Up: [datalog], [negation], [datalog_extensions] + +Aliases: datalog with negation diff --git a/datalog_negation_provenance b/datalog_negation_provenance @@ -0,0 +1,7 @@ +# Datalog negation provenance + +[bogaerts2025why] + +Up: [datalog_negation], [datalog_provenance] + +Aliases: datalog provenance negation diff --git a/dd b/dd @@ -7,6 +7,6 @@ Up: [d], [knowledge_compilation] -Aliases: dds +Aliases: dds, d d, d ds See also: [ddnnf_vs_dd] diff --git a/derivation b/derivation @@ -0,0 +1,13 @@ +# Derivation + +A *derivation* for a [CFG] G is a sequence of [protowords] starting at the [axiom] and where at every step some [nonterminal] is replaced by the [RHS] of a [production] for that [nonterminal]. If the derivation ends in a [word] w without [nonterminals], then it witnesses that w is in the [language_accepted_by] G + +Notion of [left_derivation], which is in bijection with [derivation_trees] + +- [derivation_index] + +Up: [context_free_grammar] + +See also: [derivation_tree] + +Aliases: derivations diff --git a/derivation_index b/derivation_index @@ -0,0 +1,11 @@ +# Derivation index + +The *index* of a [derivation] is the maximal number of [nonterminals] occurring in the [protowords] of the [derivation] + +Mentioned in [esparza2016brief], attributed to [ginsburg1968derivation] + +If you bound it on [CFGs] on all derivations, you get [ultralinear_CFGs] + +If you bound it by requiring that every accepted word has a derivation of bounded index, you get [finite_index_CFGs] + +Up: [derivation] diff --git a/derivation_tree b/derivation_tree @@ -6,6 +6,8 @@ The [yield] of a derivation tree is the sequence of its [leaves] The notion of derivation trees also occurs in [datalog]: [derivation_tree_datalog] +- [derivation_tree_index] + Up: [tree] for [context_free_grammar] Aliases: parse tree, derivation trees, parse trees diff --git a/derivation_tree_index b/derivation_tree_index @@ -0,0 +1,9 @@ +# Derivation tree index + +The *index* of a [derivation_tree] is the minimal index of its [derivations] (defined in [esparza2016brief] Section 3.2) + +It is connected to its [Strahler_number] if the grammar is in [Chomsky_normal_form] + +Up: [derivation_tree] + +See also: [chytil1990caterpillars] diff --git a/dynamic_word b/dynamic_word @@ -3,7 +3,8 @@ A [word] on which we can apply [updates_word] - [dynamic_membership_word] +- [pattern_matching_dynamic] Up: [word] -Aliases: dynamic words, dynamic string, dynamic strings +Aliases: dynamic words, dynamic string, dynamic strings, dynamic text, dynamic texts diff --git a/enumeration_spanner b/enumeration_spanner @@ -5,4 +5,4 @@ Up: [enumeration] for [spanner] -See also: [enumeration_strings] +See also: [enumeration_strings], [regular_expression_pattern_matching_problem] diff --git a/equivalence_automata_pushdown_deterministic b/equivalence_automata_pushdown_deterministic @@ -9,3 +9,5 @@ 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 + +See also: [context_free_grammar_unambiguous_equivalence_problem] diff --git a/formal_language_computational_problems b/formal_language_computational_problems @@ -12,6 +12,6 @@ Up: [formal_language] -Aliases: formal language computational problem +Aliases: formal language computational problem, formal language problem, formal language problems See also: [Computational_problems_on_words] diff --git a/graph_problem b/graph_problem @@ -26,6 +26,7 @@ - [graph_sandwich_problem] - [planarity_testing] - [recognition_problem] +- [graph_realization_problem] Up: [computational_problem] on [graph] diff --git a/graph_realization_problem b/graph_realization_problem @@ -0,0 +1,14 @@ +# Graph realization problem + +https://en.wikipedia.org/wiki/Graph_realization_problem + +[computational_problem] on [undirected_graphs] + +Can be solved in [PTIME] + +- [graph_realization_problem_digraph] +- [graph_realization_problem_bipartite] + +Up: [graph_problem] + +See also: [degree] diff --git a/graph_realization_problem_bipartite b/graph_realization_problem_bipartite @@ -0,0 +1,9 @@ +# Graph realization problem bipartite + +https://en.wikipedia.org/wiki/Bipartite_realization_problem + +in [PTIME] but the partition into the two sides is given (= as two degree sequences) + +if the partition is not given (= given a degree sequence, is there a [bipartite_graph] that achieves it), the complexity is [open_problem], cf [miklos2025complexity] + +Up: [graph_realization_problem], [bipartite_graph] diff --git a/graph_realization_problem_digraph b/graph_realization_problem_digraph @@ -0,0 +1,7 @@ +# Graph realization problem digraph + +https://en.wikipedia.org/wiki/Digraph_realization_problem + +in [PTIME] + +Up: [graph_realization_problem], [directed_graph] diff --git a/k_mismatch_pattern_matching b/k_mismatch_pattern_matching @@ -0,0 +1,7 @@ +# K mismatch pattern matching + +[gawrychowski2018towards] + +Up: [approximate_pattern_matching] + +See also: [k_edit_pattern_matching] diff --git a/language_distance_problem b/language_distance_problem @@ -0,0 +1,5 @@ +# Language distance problem + +Given a [formal_language] and a [word], compute the [string_distance] of the [word] to the [formal_language] + +Up: [regular_language_membership] diff --git a/length_universality b/length_universality @@ -0,0 +1,7 @@ +# Length universality + +- [Length_universality_automata] + +See also: [universality_problem] + +Up: [formal_language_problem] diff --git a/membership_problem b/membership_problem @@ -7,8 +7,13 @@ given [formal_language] L description and [word] w, test if w belongs to L - [pattern_language_membership] - [context_free_language_membership] -- [radoszewski2021hardness] for hardness under [3SUM_conjecture] of testing membership of a string to some [formal_languages] +- [radoszewski2021hardness] for hardness under [3SUM_conjecture] of testing membership of a [word] to some [formal_languages] + +Generalizations: +- [probabilistic_membership_problem] Up: [formal_language_computational_problem] Aliases: formal language membership problem, formal language membership, language membership, language membership problem + +See also: [word_problem] diff --git a/min_plus_matrix_multiplication b/min_plus_matrix_multiplication @@ -0,0 +1,5 @@ +# Min plus matrix multiplication + +discussed in [chi2022faster] + +Up: [matrix_multiplication], [min_plus_semiring] diff --git a/parikhs_theorem b/parikhs_theorem @@ -7,3 +7,5 @@ https://en.m.wikipedia.org/wiki/Parikh's_theorem The [Parikh_image] of a [CFL] is a [union] of finitely many [linear_sets], where a [linear_set] is an expression of the form u + M alpha over alpha the vectors with integer values, for u an origin vector and M a [matrix] Up: [theorem] about [parikh_image] + +See also: [CFL_commutative_closure_regular] diff --git a/partial_word b/partial_word @@ -0,0 +1,11 @@ +# Partial word + +A [word] where some positions are specified and others are [don't_cares] + +Studied in [berstel1999partial] and in [amarilli2026complexity] + +Up: [word] + +See also: [probabilistic_word] + +Aliases: partial words diff --git a/pattern_matching b/pattern_matching @@ -32,6 +32,7 @@ - [pattern_matching_dontcare] when allowing [dontcares] (one single symbol can be anything) - [pattern_matching_compressed] on [compressed_data] - [gapped_pattern_matching]: find two patterns separated by a distance within a specified range +- [text_index], when the text can be preprocessed ## Implementations diff --git a/pattern_matching_practice b/pattern_matching_practice @@ -1,6 +1,6 @@ # Pattern matching practice -- https://smart-tool.github.io/smart/ +- [smart_tool]: https://smart-tool.github.io/smart/ - [strstr] - uses [two_way_string_matching_algorithm]? diff --git a/pattern_matching_realtime b/pattern_matching_realtime @@ -1,7 +0,0 @@ -# Pattern matching realtime - -on text which arrives in streaming: [realtime] - -- [kucherov2013full]: pattern matching in [linear_time] in the pattern + number of occurrences on [dynamic_data] (with append in O(1) worst case) - -Up: [pattern_matching_dynamic], [realtime] diff --git a/pattern_matching_streaming b/pattern_matching_streaming @@ -1,5 +0,0 @@ -# Pattern matching streaming - -you get the pattern character by character and must build a [sketching] of the pattern, and then you get the text character by character and must match - -Up: [approximate_pattern_matching_streaming] diff --git a/probabilistic_membership_problem b/probabilistic_membership_problem @@ -0,0 +1,7 @@ +# Probabilistic membership problem + +Having fixed a [formal_language], given a [probabilistic_word], what is the probability of the outcomes that belong to the language + +Studied in [amarilli2026complexity] + +Up: [membership_problem], [PQE] diff --git a/probabilistic_word b/probabilistic_word @@ -0,0 +1,13 @@ +# Probabilistic word + +A [word] where each position specifies a [probability_distribution] on letters + +Studied in [amarilli2026complexity] + +- [probabilistic_membership_problem] + +Up: [word] + +See also: [partial_word], [tuple_independent_database] + +Aliases: weighted sequence, weighted string, weighted sequences, weighted strings, probabilistic words, position weight matrix, position weight matrixes diff --git a/production b/production @@ -8,3 +8,5 @@ A pair of [proto_words]: expresses that the [LHS] can be rewritten to the [RHS] Up: [formal_grammar] Aliases: productions + +See also: [derivation] diff --git a/proto_word b/proto_word @@ -3,3 +3,5 @@ A *proto word* is a [word] on the extended [alphabet] consisting of [terminals] and [nonterminals] Up: [context_free_grammar] + +Aliases: proto words, protoword, protowords diff --git a/provenance_datalog b/provenance_datalog @@ -13,4 +13,9 @@ Subcases: - [calautti2023complexity]: [provenance_membership_testing] - [convergence] for [datalog]: [abokhamis2021convergence] +For [datalog_extensions]: +- [datalog_negation_provenance] + +- [bogaerts2025why] pour [datalog_with_negation] + Up: [provenance], [datalog] diff --git a/regular_language_membership b/regular_language_membership @@ -6,3 +6,5 @@ - [regular_expression_matching] Up: [membership_problem] for [regular_language] + +See also: [language_distance_problem] diff --git a/square_word b/square_word @@ -6,4 +6,4 @@ Up: [word] See also: [twin], [square_free_word], [square_language], [non_square_word], [repetitive_string], [Shuffle_square], [cube_word] -Aliases: word square, word squares +Aliases: word square, word squares, string square, string squares diff --git a/strahler_number b/strahler_number @@ -4,6 +4,11 @@ https://en.wikipedia.org/wiki/Strahler_number cf [esparza2016brief] +- [strahler_number_formal_language] + +Related to [pathwidth] by a factor of 2 +- cf https://en.wikipedia.org/wiki/Strahler_number#Pathwidth + Up: [parameter] on [tree] -See also: [cantor_bendixson_rank] +See also: [cantor_bendixson_rank], [ganardi2025complexity] diff --git a/strahler_number_formal_language b/strahler_number_formal_language @@ -0,0 +1,5 @@ +# Strahler number formal language + +[derivation_tree_index] + +Up: [strahler_number], [formal_language_theory] diff --git a/substitution b/substitution @@ -0,0 +1,7 @@ +# Substitution + +An [update_word] where you change a single character + +Up: [update_word] + +Aliases: relabeling update, substitution update, relabeling updates, substitution updates diff --git a/tropical_semiring b/tropical_semiring @@ -12,4 +12,4 @@ Up: [semiring_list] See also: [mpp_minimum], [tropical], [max_plus_semiring] -Aliases: semiring tropical +Aliases: semiring tropical, min plus semiring, semiring min plus diff --git a/universality_problem b/universality_problem @@ -7,6 +7,6 @@ Up: [computational_problem], [formal_language] -See also: [language_emptiness] +See also: [language_emptiness], [length_universality] Aliases: language universality, language universality problem diff --git a/update_word b/update_word @@ -7,7 +7,7 @@ - [push_operation] on one side and [pop_operation] on the other - cf [queue] - cf [sliding_window] -- [word_split]: related to [cut_and_paste] +- [word_split]: related to [cut_and_paste_updates] Up: [update] for [word] diff --git a/word b/word @@ -12,6 +12,8 @@ Generalizations: - [data_word] - [dynamic_word] - [infinite_word] +- [partial_word] +- [probabilistic_word] Operations: - [concatenation]