commit 6d1caa31e51af465ecea685eb09bea394dff51c6
parent db15a81122346cb363dd2b8ff1e9017da4687509
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 29 Apr 2026 22:29:25 +0200
Merge remote-tracking branch 'origin/master'
Diffstat:
26 files changed, 97 insertions(+), 35 deletions(-)
diff --git a/cernys_conjecture b/cernys_conjecture
@@ -0,0 +1,7 @@
+# Cerny's conjecture
+
+https://en.wikipedia.org/wiki/Synchronizing_word#Length
+
+Up: [synchronizing_word], [open_problem]
+
+Aliases: Cerny conjecture
diff --git a/cfg_multiplicity_equivalence b/cfg_multiplicity_equivalence
@@ -0,0 +1,13 @@
+# CFG multiplicity equivalence
+
+Two [CFGs] G1 and G2 are *multiplicity equivalent* if they recognize the same language with the same number of [parse_trees] for each [word]
+
+[Decision_problem]: [cfg_multiplicity_equivalence_problem]
+
+See [kuich2005multiplicity]
+
+Up: [CFG_equivalence]
+
+Aliases: multiplicity equivalent
+
+See also: [bag_semantics]
diff --git a/cfg_multiplicity_equivalence_problem b/cfg_multiplicity_equivalence_problem
@@ -0,0 +1,9 @@
+# CFG multiplicity equivalence problem
+
+The [equivalence_problem] on [CFGs] but for deciding [CFG_multiplicity_equivalence]
+
+It is an [open_problem] whether this is decidable
+
+See [kuich2005multiplicity]
+
+Up: [context_free_grammar_unambiguous_equivalence_problem]
diff --git a/context_free_grammar_unambiguous_equivalence_problem b/context_free_grammar_unambiguous_equivalence_problem
@@ -1,10 +1,12 @@
-# Context free grammar unambiguous equivalence problem
+# Unambiguous CFG equivalence problem
-It is an [open_problem] whether CFG equivalence is decidable when the input are two [uCFGs]. Same thing for the problem on arbitrary [CFGs] where we want equivalence in [bag_semantics] i.e., do the two [CFGs] recognize the same language with the same number of [parse_trees] for each [word]?
+It is an [open_problem] whether CFG equivalence is decidable when the input are two [uCFGs]. More general problem: [CFG_multiplicity_equivalence]
cf https://cstheory.stackexchange.com/questions/38598/is-equivalence-of-unambiguous-context-free-languages-decidable
-By contrast [language_inclusion] is [undecidable] because [DPDA_inclusion] is [undecidable]
+By contrast:
+- [language_inclusion] is [undecidable] because [DPDA_inclusion] is [undecidable]
+- equivalence of a [UCFG] with a [regular_language] is [decidable] according to [jez2013unambiguous] p2
Up: [context_free_grammar_equivalence_problem], [uCFGs]
diff --git a/counter_free_automata b/counter_free_automata
@@ -9,3 +9,5 @@ Such automata recognize the [aperiodic_languages]
Up: [automata_classes]
Aliases: automata counter-free, automata counter free, automaton counter free
+
+See also: [permutation_automaton]
diff --git a/description_logics b/description_logics
@@ -2,7 +2,9 @@
A set of lightweight [logics] with different complexity depending on the features allowed.
-[Survey_paper]: [artale2009dllite]
+[Survey_papers]:
+- [artale2009dllite]
+- [krotzsch2013description]
Classes:
- [DL_Lite]
diff --git a/dpda_inclusion b/dpda_inclusion
@@ -0,0 +1,10 @@
+# DPDA inclusion
+
+It is [undecidable], cf [ginsburg1965deterministic] Theorem 5.3 (b)
+or [asveld2000inclusion].
+
+See also: [context_free_grammar_unambiguous_equivalence_problem]
+
+Up: [language_inclusion_problem], [DPDA]
+
+Aliases: DPDA inclusion problem
diff --git a/equivalence_automata_pushdown_deterministic b/equivalence_automata_pushdown_deterministic
@@ -1,4 +1,4 @@
-# Equivalence automata pushdown deterministic
+# Deterministic Pushdown Automaton Equivalence
Was shown [decidable] by [senizergues1997equivalence]
@@ -8,6 +8,6 @@ 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
+Aliases: automaton equivalence deterministic pushdown automaton, automaton equivalence pushdown automaton deterministic, dpda equivalence, dpda equivalence problem, Deterministic Pushdown Automaton Equivalence
See also: [context_free_grammar_unambiguous_equivalence_problem]
diff --git a/factor b/factor
@@ -1,6 +1,6 @@
# Factor
-Definition: [word] u is factor of [word] v if we have v = xuy for some [words] x and y
+Definition: a [word] u is a *factor* of [word] v if we have v = xuy for some [words] x and y
- [factor_universal]
- [factorial_language]
@@ -14,6 +14,6 @@ If u is a factor of v, then v is an [extension] of u
Up: [formal_language_theory]
-See also: [subword], [prefix], [suffix], [factor_avoidance]
+See also: [subword], [prefix], [suffix], [factor_avoidance], [extension]
Aliases: factors, infix, infixes
diff --git a/factor_closed_language b/factor_closed_language
@@ -6,4 +6,4 @@ Also closed "bifix-closed", because it is equivalent to being [prefix_closed] an
Up: [factor]
-See also: [factor_convex_language], [Prefix_closed_language], [Suffix_closed_language], [factor_free_language], [bifix_free_language], [bifix_convex_language]
+See also: [factor_convex_language], [Prefix_closed_language], [Suffix_closed_language], [factor_free_language], [bifix_free_language], [bifix_convex_language], [two_sided_ideal]
diff --git a/graph_labeling b/graph_labeling
@@ -6,3 +6,5 @@
- [canonical_labeling]
Up: [graph]
+
+Aliases: labeling scheme
diff --git a/graph_square b/graph_square
@@ -10,6 +10,8 @@ Three variants:
- connecting vertices with a [walk] of length *exactly* two (but potentially also an edge): this is [graph_exact_square]
- connecting vertices with a distance *exactly* two: this is [graph_exact_distance_square]
+The square of the [line_graph], and the [line_graph] of the square, are essentially always [Hamiltonian] for [connected_graphs], cf [nebesky1973line]
+
Up: [graph_exponentiation]
See also: [radoszewski2011hamiltonian], [graph_cube], [graph_square_root], [graph_exact_square]
diff --git a/inverse_automaton b/inverse_automaton
@@ -0,0 +1,7 @@
+# Inverse automaton
+
+A [DFA] where every letter defines a [partial_bijection] on the set of [states]
+
+Studied in [birget1994pspace]
+
+Up: [permutation_automaton]
diff --git a/language_inclusion b/language_inclusion
@@ -1,4 +1,4 @@
-# Language inclusion
+# Language inclusion problem
- [pattern_language_inclusion]
- [language_inclusion_bounded]
@@ -7,3 +7,5 @@
- [CFG_language_inclusion]
Up: [formal_language_computational_problems], [set_inclusion]
+
+Aliases: language inclusion problem
diff --git a/line_graph b/line_graph
@@ -8,6 +8,8 @@ They can be recognized in [linear_time]
They have a [Hamiltonian_cycle] if the original graph has a [Hamiltonian_cycle]: cf [balakrishnan2012textbook], Corollary 6.5.5 and [harary1965eulerian]
+The [graph_square] of the line graph, and the line graph of the [graph_square], are essentially always [Hamiltonian] for [connected_graphs], cf [nebesky1973line]
+
Up: [graph_basic_notions]
See also: [dual_hypergraph], [dual_graph], [incidence_graph]
diff --git a/matching b/matching
@@ -1,16 +1,16 @@
# Matching
-Structure in [graph] et [graph_bipartite]: a subset of edges where no two edges share a vertex
+Structure in [graphs] and [bipartite_graphs]: a subset of [edges] where no two [edges] share a common [vertex]
- [maximum_matching]
- [perfect_matching]
-Problems:
+[Computational_problems]:
- [matching_counting]
- [maximum_matching_counting]
-Algorithms [graph_algorithm]:
+[Graph_algorithms]:
- [hungarian_algorithm]
@@ -22,7 +22,7 @@ Variants:
Also the [linear_relaxation]: see [fractional_edge_packing]
-See also: [independent_set], [induced_matching], [graph_matching_covered], [deficiency]
+See also: [independent_set], [induced_matching], [graph_matching_covered], [deficiency], [partial_bijection]
Up: [graph_substructure]
diff --git a/open_world_query_answering b/open_world_query_answering
@@ -26,7 +26,7 @@ negation of a [conjunctive_query] or [union_of_conjunctive_queries]).
Also called "ontology-based data access", see also [ontology_mediated_query]
-- [query_rewriting]
+- [open_world_query_rewriting]
- [chase]
- [combined_complexity] approaches, for instance [gottlob2023polynomial]
diff --git a/partial_order b/partial_order
@@ -7,6 +7,7 @@ Variants:
- [poset_rank]
- [partial_order_dimension]
- connections to [treewidth]
+- [boolean_dimension]
- [crown] and link with [partial_order_dimension]
- [trotter1973dimension]
- [order_type]
diff --git a/permutation_automaton b/permutation_automaton
@@ -2,6 +2,10 @@
https://en.wikipedia.org/wiki/Permutation_automaton
-See also: [language_group]
+Generalization: [inverse_automaton]
+
+See also: [language_group], [Counter_free_automata]
Up: [automata], [permutation]
+
+Aliases: pure group automata, puregroup automata, pure group automaton, puregroup automaton, group automata, permutation automata, group automaton
diff --git a/poset_width b/poset_width
@@ -6,4 +6,4 @@ Can be computed in [PTIME] via [dilworths_theorem] using a [flow_algorithm]
Up: [partial_order]
-See also: [dilworths_theorem], [chain_partitioning], [partial_order_height]
+See also: [dilworths_theorem], [chain_partitioning], [partial_order_height], [poset_dimension]
diff --git a/right_extension b/right_extension
@@ -4,4 +4,4 @@ A [word] u is a *right extension* of a [word] v iff v is a [prefix] of u
Up: [prefix]
-See also: [distinguishing_extension]
+See also: [distinguishing_extension], [extension]
diff --git a/straight_line_program b/straight_line_program
@@ -3,6 +3,7 @@
essentially a [context_free_grammar] that generates a single [string]: [acyclicity] requirement plus only one [production] per [nonterminal]
- [enumeration_slp]
+- [direct_access_slp], cf [munoz2026dynamic]
- [smallest_grammar_problem]
- [slp_balancing]
diff --git a/streaming b/streaming
@@ -1,15 +0,0 @@
-# Streaming
-
-- sequence of data items arrives one item after the other
- - specific kind of [update_word] when you can only append to the right
- - particular case of [sliding_window], in which you can also pop at the right
-- [enumeration_streaming]
-- [dynamic_membership_streaming] discussed in [ganardi2024regular]
-
-also work on [sampling], [distinct_element], etc.
-
-- possible variants:
- - are results produced immediately, or only at the end of the stream?
- - is the stream length bounded? is it known in advance?
-
-Up: [algorithms]
diff --git a/synchronizing_word b/synchronizing_word
@@ -1,7 +1,7 @@
# Synchronizing word
-- [cerny_conjecture] Cerny's conjecture about the existence of synchronizing words on DFAs
+- [Cerny's_conjecture] about the existence of synchronizing words on [DFAs]
Up: [automata]
-See also: [mortal_word], [meeting_time], [synchronizing_sets], [synchronizing_word_problem], [completely_reachable_automata]
+See also: [mortal_word], [meeting_time], [synchronizing_sets], [synchronizing_word_problem], [completely_reachable_automata], [ideal]
diff --git a/unbalanced_orthogonal_vectors b/unbalanced_orthogonal_vectors
@@ -0,0 +1,9 @@
+# Unbalanced orthogonal vectors
+
+Defined in [bringmann2018multivariate] hypothesis 2.3
+
+See [bringmann2021translating]
+
+Up: [orthogonal_vectors], [unbalanced]
+
+Aliases: UOV
diff --git a/vertex_unbalanced_triangle_listing b/vertex_unbalanced_triangle_listing
@@ -7,3 +7,5 @@ Implied by [3sum_conjecture]
Up: [triangle_listing]
Aliases: VUTL
+
+See also: [unbalanced_orthogonal_vectors]
