commit cf4c4caedece8da081b224d73dd7ed4255061903 parent 5755d442c9f9b5b416180689fff3fdbdbca92ced Author: Antoine Amarilli <a3nm@a3nm.net> Date: Tue, 11 Aug 2026 22:49:14 +0200 Merge remote-tracking branch 'origin/master' Diffstat:
37 files changed, 145 insertions(+), 17 deletions(-)
diff --git a/automata_determinization b/automata_determinization @@ -11,6 +11,8 @@ The bound on [state_complexity] is exactly 2^n: some [NFAs] on a binary alphabet Bounds for specific [automata_classes]: - [unary_ufa] -Up: [automata_constructions] +Up: [automata_constructions], [automaton_deterministic] -Aliases: automata determinized, determinization, automaton determinize, automata determinize, automaton determinized, determinized +Aliases: automata determinized, determinization, automaton determinize, automata determinize, automaton determinized, determinized, automaton determinization + +See also: [unambiguization] diff --git a/automata_min_plus b/automata_min_plus @@ -6,6 +6,8 @@ The [deterministic_automata] in this model are less powerful than the [nondeterm It is [decidable] whether an input min-plus automata is equivalent to a [deterministic_automaton] in this setting, cf [almagor2025determinization] and [almagor2026complexity] +- [min_plus_automata_equivalence] + Up: [automata_weighted] See also: [min_plus_matrix_multiplication], [Tropical_semiring] diff --git a/automata_weighted b/automata_weighted @@ -19,6 +19,7 @@ Schützenberger, 1961 - [automata_weighted_conjugacy] - [automata_min_plus] +- [automata_weighted_equivalence] Up: [automata] diff --git a/automata_weighted_equivalence b/automata_weighted_equivalence @@ -0,0 +1,11 @@ +# Equivalence of weighted automata + +see [daviaud2020containment] + +- [min_plus_automata_equivalence] + +Up: [automaton_equivalence], [weighted_automata] + +Aliases: Equivalence of weighted automata + +See also: [automata_weighted_inclusion] diff --git a/automata_weighted_inclusion b/automata_weighted_inclusion @@ -0,0 +1,9 @@ +# Inclusion of weighted automata + +see [daviaud2020containment] + +See also: [automata_weighted_equivalence] + +Up: [automata_inclusion], [weighted_automata] + +Aliases: Inclusion of weighted automata, Containment of weighted automata diff --git a/automaton_complete b/automaton_complete @@ -8,6 +8,6 @@ We can do [automaton_completion] to transform an [incomplete_automata] into a co Up: [automata_types] -Aliases: complete automaton, complete automata +Aliases: complete automaton, complete automata, complete DFA, complete DFAs See also: [automaton_trimmed] diff --git a/automaton_equivalence b/automaton_equivalence @@ -7,6 +7,8 @@ Special case: [automaton_universality] +Generalizations: [automata_weighted_equivalence] + Up: [automata_problems] See also: [language_equivalence], [automaton_inclusion], [query_equivalence_problem], [regular_language_equivalence] diff --git a/automaton_inclusion b/automaton_inclusion @@ -17,4 +17,4 @@ Up: [automata_problems], [language_inclusion] See also: [automaton_equivalence], [automaton_universality] -Aliases: regular language inclusion +Aliases: regular language inclusion, automata inclusion, automaton containment, automata containment diff --git a/bipartite_perfect_matching b/bipartite_perfect_matching @@ -0,0 +1,7 @@ +# Bipartite perfect matching + +A [perfect_matching] in a [bipartite_graph] + +- [bipartite_perfect_matching_problem] + +Up: [perfect_matching], [bipartite_graph] diff --git a/bipartite_perfect_matching_problem b/bipartite_perfect_matching_problem @@ -0,0 +1,5 @@ +# Bipartite perfect matching problem + +The [computational_problem] of deciding whether a [bipartite_graph] admits a [bipartite_perfect_matching] + +Up: [perfect_matching_problem], [bipartite_perfect_matching] diff --git a/context_free_language_unambiguous b/context_free_language_unambiguous @@ -7,4 +7,4 @@ Special cases: Up: [context_free_language] -Aliases: uCFL, uCFLs, unambiguous CFL, unambiguous CFLs, unabiguous context free language, unambgiuous context free languages +Aliases: uCFL, uCFLs, unambiguous CFL, unambiguous CFLs, unambiguous context free language, unambiguous context free languages diff --git a/detour_problem b/detour_problem @@ -6,4 +6,6 @@ Given a [directed_graph] and s and t, decide if there is a [simple_path] from s Related work on [induced_paths] in [undirected_graphs]: [berger2021finding] +[PTIME] algorithm in [chen2026polynomial] + Up: [shortest_path] diff --git a/exact_matching b/exact_matching @@ -9,4 +9,6 @@ Variants: - [exact_matching_parity] - [red_blue_yellow_matching] -Up: [matching] +Up: [matching_problem] + +Aliases: exact matching problem diff --git a/external_memory b/external_memory @@ -3,4 +3,8 @@ Papers looking at the [input_output_complexity] of [algorithms] - cf [vitter2008algorithms] +from [yuan2024io] +- [katriel2003elementary] for [BFS] in external memory +- [zheng2015flashgraph] for [semi_external_memory] + Up: [machine_model] diff --git a/factor b/factor @@ -16,4 +16,4 @@ Up: [formal_language_theory] See also: [subword], [prefix], [suffix], [factor_avoidance], [extension] -Aliases: factors, infix, infixes +Aliases: factors, infix, infixes, word factor diff --git a/graph_database_practical b/graph_database_practical @@ -5,6 +5,7 @@ Implementations: - [Neo4j] - for [RPQs]: [garcia2025pathdb] - [apache_jena] +- [amazon_neptune] for [hosted_solution] Query languages: @@ -14,6 +15,8 @@ Models: - [Property_graphs]: nodes and directed edges which have an ID and takes a value from some property +Comparisons: [besta2023demistifying] + Up: [graph_database] See also: [triple_store] diff --git a/halls_theorem b/halls_theorem @@ -1,6 +1,7 @@ # Hall's theorem In a [bipartite_graph] (X, Y), there is a [matching] incident to each [vertex] of X iff for each [subset] W of X, we have |W| \leq |Neighbors(W)|. +- notion of hall blocker: if a [bipartite_graph] has not [perfect_matching] then... cf https://blog.computationalcomplexity.org/2026/07/bipartite-perfect-matching-in.html?m=1 [Hall's_theorem_proof] diff --git a/label_constrained_reachability b/label_constrained_reachability @@ -0,0 +1,10 @@ +# Label constrained reachability + +a special case of [RPQ] on [graphs] + +- [peng2020answering] for [state_of_the_art] according to [yuan2024io] +- [yuan2024io] for [external_memory] +- [zheng2015flashgraph] for [semi_external_memory] +- [katriel2003elementary] for [BFS] in [external_memory] + +Up: [reachability] diff --git a/matching b/matching @@ -7,6 +7,8 @@ Structure in [graphs] and [bipartite_graphs]: a subset of [edges] where no two [ [Computational_problems]: +- [matching_problem] + - [exact_matching_problem] - [matching_counting] - [maximum_matching_counting] diff --git a/minimization_automaton b/minimization_automaton @@ -5,6 +5,6 @@ Up: [minimization] of [automaton] -Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata, automaton minimal, minimal automaton +Aliases: minimization of automata, automata minimization, automaton minimization, minimization automata, automaton minimal, minimal automaton, automaton minimisation, automata minimisation See also: [canonical_labeling], [canonical_DFA] diff --git a/nc b/nc @@ -15,4 +15,11 @@ It is assumed but unknown that [nc] neq [ptime] - [nc0] - [nc1] +recently shown to contain the [bipartite_perfect_matching_problem] +- https://blog.computationalcomplexity.org/2026/07/bipartite-perfect-matching-in.html?m=1 +- an example of [derandomization] as it was known to be in [randomized_NC] + +contains the [det] problem of computing the [determinant] of a [matrix] +- cf https://blog.computationalcomplexity.org/2026/07/bipartite-perfect-matching-in.html?m=1 + Up: [ac] diff --git a/overlap_word b/overlap_word @@ -0,0 +1,9 @@ +# Overlap word + +according to [guaypquet2009avoiding] + +a [factor] in a [word] of the form axaxa with a a letter and x a possibly empty [word] + +there are infinite words over a binary alphabet that contain no overlaps + +Up: [square_word] diff --git a/perfect_matching b/perfect_matching @@ -8,6 +8,9 @@ A [matching] where every vertex is incident to an edge of the matching Graphs with unique [perfect_matching]: [Kotzig's_theorem] +- [bipartite_perfect_matching] +- [perfect_matching_problem] + Up: [matching] See also: [matching_counting], [f_factor] diff --git a/perfect_matching_problem b/perfect_matching_problem @@ -0,0 +1,8 @@ +# Perfect matching problem + +The [computational_problem] of deciding whether an [undirected_graph] admits a [perfect_matching] + +- [bipartite_perfect_matching_problem] +- [maximum_matching_problem] + +Up: [computational_problem], [perfect_matching] diff --git a/prime_number b/prime_number @@ -6,6 +6,6 @@ Up: [arithmetic] -See also: [prime_implicant], [polynomial_irreducible], [twin_prime_conjecture], [goldbach_conjecture], [primitive_word], [twin_primes] +See also: [prime_implicant], [polynomial_irreducible], [twin_prime_conjecture], [goldbach_conjecture], [primitive_word], [twin_primes], [prime_number_repartition] -Aliases: prime numbers +Aliases: prime numbers, prime, primes diff --git a/prime_number_repartition b/prime_number_repartition @@ -0,0 +1,9 @@ +# Prime number repartition + +[asymptotic] distribution of [prime_numbers] + +- [prime_number_theorem] + +Up: [prime_number] + +See also: [riemann_hypothesis] diff --git a/prime_number_theorem b/prime_number_theorem @@ -1,6 +1,6 @@ # Prime number theorem -[theorem] by Hadamard and La Vallée Poussin about [asymptotic] distribution of [prime_number] +[theorem] by Hadamard and La Vallée Poussin about [prime_number_repartition] inequality without asymptotics: [rosser1962approximate], 3.13 diff --git a/primitive_word_context_free b/primitive_word_context_free @@ -0,0 +1,9 @@ +# Primitive word context free + +It is an [open_problem] whether the [language_of_primitive_words] is a [CFL] +- it is known that it is not a [uCFL] by [petersen1996language] +- it is known that it is not a [linear_CFL] by [horvath1995strong] + +cf https://a3nm.net/work/research/questions/#context-freeness-of-primitive-words + +Up: [open_problem] on [primitive_word_language] diff --git a/primitive_word_language b/primitive_word_language @@ -2,7 +2,7 @@ The [formal_language] of all [primitive_words] -It is an [open_problem] whether it is a [CFL], but it is known that it is not a [uCFL] by [petersen1996language] and not a [linear_CFL] by [horvath1995strong] +[open_problem]: [primitive_word_context_free] Discussed in [lischke2011primitive] @@ -12,4 +12,4 @@ Up: [formal_language], [primitive_word] See also: [square_language], [composite_word_language], [formal_language_primality] -Aliases: primitive words language +Aliases: primitive words language, language of primitive words diff --git a/reachability b/reachability @@ -5,6 +5,7 @@ - [reachability_single_source] - [reachability_all_pairs] - [VASS_reachability] +- [label_constrained_reachability] Up: [computational_problem], [graph_theory] diff --git a/sequence b/sequence @@ -13,6 +13,13 @@ - [subsequence] +## Types + +- [arithmetic_sequence] +- [geometric_sequence] +- [arithmetico_geometric_sequence] +- [constant_recursive_sequence] + ## Open problems - [skolem_problem] diff --git a/sidon_set b/sidon_set @@ -6,4 +6,4 @@ set of [natural_numbers] where all pairwise [sums] are unique Up: [combinatorics] -See also: [golomb_ruler] +See also: [golomb_ruler], [sum_free_set] diff --git a/square b/square @@ -4,6 +4,6 @@ Up: [geometry] -See also: [squaring] +See also: [squaring], [square_word] Aliases: squares diff --git a/square_free_word b/square_free_word @@ -2,6 +2,11 @@ A [word] which does not contain a nonempty [factor] which is a [square], i.e.,a [word] which is not a [repetitive_string] +There are infinite square-free words over a ternary alphabet + +We can generate them by backtracking, this gives the [lexicographically] smallest such word, i.e., the [lexicographically_smallest_squarefree_ternary] +- if we disallow backtracking, we get an infinite square-free word with the natural numbers as alphabet, which is in fact the [ruler_sequence] + Up: [square_word], [factor_avoidance] See also: [square_free_word_language], [repetitive_string], [thue_morse_sequence], [cube_free_word] diff --git a/square_word b/square_word @@ -4,6 +4,6 @@ A [word] of the form uu Up: [word] -See also: [twin], [square_free_word], [square_language], [non_square_word], [repetitive_string], [Shuffle_square], [cube_word] +See also: [twin], [square_free_word], [square_language], [non_square_word], [repetitive_string], [Shuffle_square], [cube_word], [overlap_word] Aliases: word square, word squares, string square, string squares diff --git a/twin_primes b/twin_primes @@ -6,4 +6,4 @@ Two numbers n, n+2 are twin primes if they are both [prime_numbers] Up: [prime_number] -See also: [prime_bounded_gaps] +See also: [prime_bounded_gaps], [prime_free_interval] diff --git a/unambiguization b/unambiguization @@ -0,0 +1,7 @@ +# Unambiguization + +see [cari2026simple] + +Up: [automata_constructions], [word_automaton_unambiguous] + +See also: [automaton_determinization]