commit 6a3902c06284558791308770071f922c40a3546f
parent 01aa58a2536a1d0b7ddb412d0f5b2afaf34f659e
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 27 Mar 2025 14:17:26 +0100
commit with codex
Diffstat:
23 files changed, 170 insertions(+), 4 deletions(-)
diff --git a/chordal b/chordal
@@ -0,0 +1,12 @@
+# Chordal
+
+https://en.wikipedia.org/wiki/Chordal_graph
+
+An [undirected_graph] is *chordal* if every [cycle] of length at least 4 has a [chord]
+
+Equivalently, an [undirected_graph] is chordal iff it has a [perfect_elimination_ordering]:
+- can be found in [linear_time] with [lexicographic_breadth_first_search]
+
+See also: [hypergraph_chordal], [proper_chordal_graph]
+
+Up: [graph]
diff --git a/context_free_grammar_finite b/context_free_grammar_finite
@@ -0,0 +1,11 @@
+# Finite CFG
+
+A *finite CFG* is a [context_free_grammar] which represents a [finite_language]
+
+Unlike general [CFGs], for finite CFGs, there always exists a [grammar_equivalent] [unambiguous_CFG]
+
+Up: [context_free_grammar], [language_finite]
+
+See also: [slp], [factorized_database]
+
+Aliases: finite context free grammar
diff --git a/direct_product b/direct_product
@@ -0,0 +1,9 @@
+# Direct product
+
+Given [structures] S1 and S2 on same [signature], the *direct product* of S1 and S2 is the [structure] where:
+- the [domain] is the [Cartesian_product] of the [domains]
+- the [tuples] are the combinations of the [tuples] of S1 and S2
+
+Up: [operator] on [structure]
+
+See also: [union]
diff --git a/dynamic_data_tree b/dynamic_data_tree
@@ -0,0 +1,7 @@
+# Dynamic data tree
+
+- [dynamic_membership_trees]
+
+various kinds of [updates]: [tree_updates]
+
+Up: [dynamic_data], [tree]
diff --git a/formal_language b/formal_language
@@ -3,6 +3,8 @@
A [set] of [words] over an [alphabet]
- [empty_language]
+- [singleton_language]
+- [finite_language]
- [regular_language]
- [weighted_language]
- [visibly_pushdown_language]
diff --git a/ganardi2024regular b/ganardi2024regular
@@ -0,0 +1,14 @@
+# Ganardi2024regular
+
+## Language classes
+
+- [length_language] Len: determined by [length]
+ - [regular_length_language]
+- [suffix_testable_language]: combinations of languages of the form Sigma^* w for a word w
+- [left_ideal]: Sigma^* L
+ - [regular_left_ideal]
+- [suffix_free_language]: If w in L then xw not in L for all non-empty x
+
+Up: [academic_paper] on [sliding_window]
+
+See also: [moses]
diff --git a/hoeffdings_inequality b/hoeffdings_inequality
@@ -0,0 +1,9 @@
+# Hoeffdings inequality
+
+https://en.wikipedia.org/wiki/Hoeffding%27s_inequality
+
+bounds deviation to [expected_value]
+
+See also: [monte_carlo]
+
+Up: [probabilities]
diff --git a/hypergraph_balanced b/hypergraph_balanced
@@ -0,0 +1,13 @@
+# Hypergraph balanced
+
+A [hypergraph] is *balanced* if the following holds: for any [induced_subhypergraph], removing the [singleton] [hyperedges], we can 2-color the [vertices] such that there is no monochromatic [hyperedge]
+
+- equivalent definition via [Berge_cycle]: every [Berge_cycle] of odd length contains a [hyperedge] containing at least three [vertices] of the cycle (like a [chord])
+
+Connection to [strongly_unimodular] [matrices] and [integer_linear_programming]
+
+Notion of [hypergraph_strongly_balanced] in [crama1986strong], equivalent to [strongly_unimodular]
+
+Up: [hypergraph]
+
+See also: [graph_bipartite], [koenig_property]
diff --git a/hypergraph_chordal b/hypergraph_chordal
@@ -0,0 +1,5 @@
+# Chordal hypergraph
+
+A [hypergraph] is *chordal* if its [primal_graph] is [chordal]
+
+Up: [hypergraph]
diff --git a/koenig_property b/koenig_property
@@ -0,0 +1,7 @@
+# Koenig property
+
+https://en.wikipedia.org/wiki/Matching_in_hypergraphs#K%C5%91nig's_property
+
+Up: [hypergraph]
+
+See also: [hypergraph_balanced]
diff --git a/myhill_nerode_equivalence b/myhill_nerode_equivalence
@@ -0,0 +1,10 @@
+# Myhill nerode equivalence
+
+For a [formal_language] L, the *Myhill-Nerode equivalence* is an [equivalence_relation] on [words] defined as follows:
+two [words] are nonequivalent if they have a [distinguishing_extension]
+
+This is similar to [syntactic_congruence] but it only considers [right_extensions]
+
+Up: [dagstuhl_regular_expressions_matching_indexing_nicola]
+
+See also: [syntactic_congruence], [automaton_minimization]
diff --git a/perfect_elimination_ordering b/perfect_elimination_ordering
@@ -0,0 +1,7 @@
+# Perfect elimination ordering
+
+A *perferct elimination ordering* of an [undirected_graph] is a [vertex_ordering] such that for every [vertex], its higher-numbered neighbors forms a [clique]
+
+See also: [chordal], [degeneracy]
+
+Up: [elimination_order]
diff --git a/prefix b/prefix
@@ -6,6 +6,7 @@
- [prefix_closed_language]
- [prefix_convex_language]
- [prefix_free_language]
+- [right_extension]
Up: [formal_language_theory]
diff --git a/primitive_root b/primitive_root
@@ -0,0 +1,7 @@
+# Primitive root
+
+Given a [word] v, returns the shortest [word] u such that v = u^k for some k
+
+Note that u is then a [primitive_word]
+
+Up: [operation] on [words]
diff --git a/primitive_word b/primitive_word
@@ -0,0 +1,9 @@
+# Primitive word
+
+A [word] which is not a [power_mathematics] of another [word]
+
+- [primitive_root]
+
+Up: [word]
+
+See also: [prime_number], [prime_number_decomposition], [primitive_word_conjecture]
diff --git a/query_evaluation_parallel b/query_evaluation_parallel
@@ -0,0 +1,5 @@
+# Query evaluation parallel
+
+[koutris2018algorithmic]
+
+Up: [query_evaluation], [database_parallelism]
diff --git a/right_extension b/right_extension
@@ -0,0 +1,7 @@
+# Right extension
+
+A [word] u is a *right extension* of a [word] v iff v is a [prefix] of u
+
+Up: [prefix]
+
+See also: [distinguishing_extension]
diff --git a/singleton_language b/singleton_language
@@ -0,0 +1,7 @@
+# Singleton language
+
+A [formal_language] that contains precisely one [word]
+
+Up: [formal_language]
+
+See also: [singleton]
diff --git a/smallest_grammar_problem b/smallest_grammar_problem
@@ -0,0 +1,11 @@
+# Smallest grammar problem
+
+The [computational_problem] of finding the smallest [CFG] that generates a specific set of [words].
+
+[np_complete]
+
+[charikar2005smallest]
+
+Up: [minimization] of [context_free_grammar]
+
+See also: [grammar_compression], [straight_line_program], [minimum_circuit_size_problem]
diff --git a/syntactic_monoid b/syntactic_monoid
@@ -4,4 +4,4 @@ Note that it is a [monoid_ordered]
Up: [monoid]
-See also: [syntactic_semigroup], [transition_monoid]
+See also: [syntactic_semigroup], [transition_monoid], [syntactic_congruence]
diff --git a/syntactic_semigroup b/syntactic_semigroup
@@ -7,6 +7,6 @@ Two definitions:
A [formal_language] is [regular_language] iff syntactic semigroup is finite
-See also: [syntactic_monoid], [non_erasing_morphism], [stable_semigroup]
+See also: [syntactic_monoid], [non_erasing_morphism], [stable_semigroup], [syntactic_congruence]
Up: [semigroup]
diff --git a/update_tree b/update_tree
@@ -0,0 +1,13 @@
+# Update tree
+
+- [relabeling]
+- [insertion_leaf]
+- [deletion_leaf]
+- [deletion_subtree]
+- [tree_split]: "cut and paste"
+
+Up: [update], [tree]
+
+See also: [update_word]
+
+Aliases: tree update, tree updates, updates tree, updates trees, update trees
diff --git a/update_word b/update_word
@@ -11,6 +11,6 @@
Up: [update] for [word]
-See also: [dynamic_word], [edit_distance_operations]
+See also: [dynamic_word], [edit_distance_operations], [update_tree]
-Aliases: updates word
+Aliases: updates word, word update, word updates
