commit cab9c7e102330c6964de5914e3627640de4b4623
parent e5282d5dc8d569fa686a40616d6a82dc6579e1e2
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 1 Aug 2025 16:32:58 +0200
commit with codex
Diffstat:
11 files changed, 58 insertions(+), 4 deletions(-)
diff --git a/canonical_labeling b/canonical_labeling
@@ -7,6 +7,8 @@ https://mathoverflow.net/a/11715
also called "graph canonization"
+The related problem of computing the [lexicographically_minimal_isomorphic_graph] is [NP_hard]
+
See also: [graph_isomorphism], [minimization_automaton], [complete_graph_invariant]
Up: [graph]
diff --git a/context_free_grammar_equivalence_problem b/context_free_grammar_equivalence_problem
@@ -4,6 +4,6 @@ The *context free grammar equivalence problem* is the [decision_problem] of test
It is [undecidable] on [CFGs], by reduction from [CFG_universality]
-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]?
+- for [uCFGs] (or with multiplicity of [parse_trees]): [context_free_grammar_unambiguous_equivalence_problem]
Up: [formal_language_computational_problem], [context_free_grammar_equivalence]
diff --git a/context_free_grammar_unambiguous b/context_free_grammar_unambiguous
@@ -4,6 +4,9 @@ An *unambiguous CFG* is a [context_free_grammar] where for every [word] in the [
[parsing] for an unambiguous CFG is more efficient
+- [unambiguous_cfg_equivalence_problem]
+- [unambiguous_cfg_universality]
+
Up: [unambiguity], [context_free_grammar]
See also: [inherently_ambiguous], [context_free_grammar_k_ambiguous], [CFG_ambiguous]
diff --git a/context_free_grammar_unambiguous_equivalence_problem b/context_free_grammar_unambiguous_equivalence_problem
@@ -0,0 +1,9 @@
+# Context free grammar unambiguous 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]?
+
+cf https://cstheory.stackexchange.com/questions/38598/is-equivalence-of-unambiguous-context-free-languages-decidable
+
+Up: [context_free_grammar_equivalence_problem], [uCFGs]
+
+Aliases: unambiguous CFG equivalence problem
diff --git a/minimization_automaton b/minimization_automaton
@@ -4,6 +4,7 @@
- https://fr.wikipedia.org/wiki/Algorithme_de_Brzozowski_de_minimisation_d%27un_automate_fini
- [hopcrofts_algorithm]
- [moores_algorithm]
+- for [NFAs]: [NFA_minimization]
Up: [minimization]
diff --git a/nfa_minimization b/nfa_minimization
@@ -0,0 +1,7 @@
+# NFA minimization
+
+https://en.wikipedia.org/wiki/NFA_minimization
+
+There is no [canonical_automaton] for [NFAs]
+
+Up: [minimization_automaton]
diff --git a/tuple_generating_dependency b/tuple_generating_dependency
@@ -1,6 +1,10 @@
# TGD
-Also called "existential rules"
+[tgd_definition]
+
+Also called "existential rules", see [existential_rules]
+
+## [Academic_papers]
- [zhang2021characterizing]: [expressiveness] of [OMQA] in various formalisms
- [carral2022normalizations] on normalization of rules
@@ -16,7 +20,7 @@ Also called "existential rules"
- [tuple_generating_dependency_frontier_guarded]
- [tuple_generating_dependency_clique_guarded]
- [tuple_generating_dependency_linear]
-- [tuple_generating_dependency_single_head]
+- [tuple_generating_dependency_single_head] and [tuple_generating_dependency_multi_head]
- [tuple_generating_dependency_sticky]
- [tuple_generating_dependency_acyclic]
- [tuple_generating_dependency_weakly_acyclic]
diff --git a/tuple_generating_dependency_linear b/tuple_generating_dependency_linear
@@ -1,11 +1,17 @@
# Tuple generating dependency linear
-[tuple_generating_dependency] where [dependency_body] consists of a single fact
+[tuple_generating_dependency] where the [dependency_body] consists of a single [atom]
It is in particular a [GTGD]
+Special cases:
+
- [inclusion_dependency]
+Generalizations:
+
+- [tuple_generating_dependency_linear_multi_head]
+
Up: [tuple_generating_dependency]
Aliases: linear TGDs, linear TGD, linear tuple-generating dependency
diff --git a/tuple_generating_dependency_multi_head b/tuple_generating_dependency_multi_head
@@ -0,0 +1,13 @@
+# Tuple generating dependency multi head
+
+A [tuple_generating_dependency] with multiple [atoms] in the [head] of the [TGDs]
+
+Studied in [gottlob2020multi]
+
+Classes:
+
+- [tuple_generating_dependency_linear_multi_head]
+
+Up: [tuple_generating_dependency]
+
+Aliases: TGD multi head, TGDs multi head, multi head TGD, multi head TGDs
diff --git a/universality_context_free_grammar b/universality_context_free_grammar
@@ -2,6 +2,8 @@
[universality_problem] for [CFGs]: it is [undecidable]
+- for [uCFGs]: [universality_context_free_grammar_unambiguous]
+
Up: [universality_problem]
See also: [universality_automata]
diff --git a/universality_context_free_grammar_unambiguous b/universality_context_free_grammar_unambiguous
@@ -0,0 +1,7 @@
+# Universality context free grammar unambiguous
+
+it is [decidable]: https://cstheory.stackexchange.com/a/41001
+
+Up: [universality_context_free_grammar], [uCFGs]
+
+Aliases: context free grammar unambiguous universality
