commit 6b1ec23969c8c44300f193fdd4bed9c187c64b0f
parent b0264b31bfab9537afeea5f032ce5562423180e3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 26 Sep 2025 07:55:33 +0200
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
11 files changed, 55 insertions(+), 11 deletions(-)
diff --git a/chase_termination b/chase_termination
@@ -1,10 +1,14 @@
# Chase termination
depends on the kind of [chase]:
-- [chase_oblivious]
-- [chase_restricted]
+- [chase_oblivious]: [oblivious_chase_termination]
+- [chase_restricted]: [restricted_chase_termination]
-recent work: [hanisch2024chase]
+depends on whether you want all instances or an input instance
+
+[academic_papers]:
+- [gogacz2014all]
+- recent work: [hanisch2024chase]
- idea: beyond [ptime] [data_complexity]
Up: [chase], [termination]
diff --git a/context_free_grammar_equivalence_problem b/context_free_grammar_equivalence_problem
@@ -2,7 +2,7 @@
The *context free grammar equivalence problem* is the [decision_problem] of testing, given two [CFGs], whether they are [CFG_equivalent]
-It is [undecidable] on [CFGs], by reduction from [CFG_universality]
+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]
diff --git a/context_free_grammar_linear b/context_free_grammar_linear
@@ -2,7 +2,10 @@
https://en.wikipedia.org/wiki/Linear_grammar
-Testing [language_emptiness] of [intersection] is already [undecidable] by reduction from [post_correspondence_problem]
+[Computational_problems]:
+- [linear_CFG_universality]
+- [linear_CFG_equivalence]
+- Testing [language_emptiness] of [intersection] is already [undecidable] by reduction from [post_correspondence_problem]
Up: [context_free_grammar]
diff --git a/context_free_language b/context_free_language
@@ -6,12 +6,13 @@
- [context_free_language_slender]
- [context_free_language_polyslender]
-Subclass:
+Subclass: [context_free_language_subclasses]
- [context_free_language_unambiguous]
- [context_free_language_deterministic]
- [context_free_language_linear]
- [context_free_language_deterministic_linear]
+- [context_free_language_unambiguous_linear]
Variants:
diff --git a/linear_cfg_equivalence b/linear_cfg_equivalence
@@ -0,0 +1,7 @@
+# Linear CFG equivalence
+
+The [context_free_grammar_equivalence_problem] on [linear_CFGs]
+
+It is [undecidable] by [baker1974reversal], cf [yehudai1980decidability]
+
+Up: [context_free_grammar_equivalence_problem], [linear_CFG]
diff --git a/linear_cfg_universality b/linear_cfg_universality
@@ -0,0 +1,7 @@
+# Linear CFG universality
+
+The [universality_problem_CFG] for [linear_CFGs]
+
+It is [undecidable] by [baker1974reversal], see [hoogeboom2015undecidable]
+
+Up: [universality_problem_CFG], [context_free_grammar_linear]
diff --git a/omqa b/omqa
@@ -8,6 +8,18 @@ subtlety: [omqa_finite] vs [omqa_unrestricted]
OMQA and [counting]: [bienvenu2022complexity]
+Approaches:
+- [chase]: materializing the entailed facts
+ - the result of the chase may be finite ([chase_termination]) or infinite
+ - it may have [bounded_treewidth]
+- [query_rewriting]
+ - can be to different [query_languages]:
+ - to [UCQs]
+ - when you have [bounded_derivation_depth]
+ - to [Datalog]
+
+OMQA with [transitive_relations]: [OMQA_transitive]
+
Up: [database_theory]
-See also: [description_logics]
+See also: [description_logics], [BDD_FC_conjecture]
diff --git a/query_rewriting b/query_rewriting
@@ -8,11 +8,16 @@ from a [query], produce a [query] which is [query_equivalent] and has some bette
- [first_order_rewriting]
- [fok_rewriting]
- [datalog_rewriting]
+- [UCQ_rewriting]
## Distiction
-Distinguish [rewriting] (an [algorithm] that can rewrite a [query_language] into another in a [computable] way) and [expressibility] ([queries] in a given [query_language] can always be expressed as a [query_equivalent] [query] in another [query_language])
+Distinguish
+- rewritability
+ - an [algorithm] that can rewrite a [query_language] into another in a [computable] way
+- [expressibility]
+ - [queries] in a given [query_language] can always be expressed as a [query_equivalent] [query] in another [query_language]
Up: [database_theory]
-See also: [query_evaluation]
+See also: [query_evaluation], [OMQA]
diff --git a/transitivity_tgds b/transitivity_tgds
@@ -7,3 +7,5 @@ Results on transitivity:
- [baget2015combining], problem with a condition for transitivity plus [linear_rules] ([existential_rule])
Up: [transitivity] for [open_world_query_answering]
+
+See also: [transitive_relations]
diff --git a/tuple_generating_dependency_multi_head b/tuple_generating_dependency_multi_head
@@ -4,10 +4,12 @@ A [tuple_generating_dependency] with multiple [atoms] in the [head] of the [TGDs
Studied in [gottlob2020multi]
+Some open questions about [chase_termination], cf [gogacz2014all]
+
Classes:
- [tuple_generating_dependency_linear_multi_head]
Up: [tuple_generating_dependency]
-Aliases: TGD multi head, TGDs multi head, multi head TGD, multi head TGDs
+Aliases: TGD multi head, TGDs multi head, multi head TGD, multi head TGDs, multiheaded rules, multi head rules, multihead rules
diff --git a/universality_context_free_grammar b/universality_context_free_grammar
@@ -3,9 +3,10 @@
[universality_problem] for [CFGs]: it is [undecidable]
- for [uCFGs]: [universality_context_free_grammar_unambiguous]
+- for [linear_CFGs]: [linear_CFG_universality]
Up: [universality_problem]
See also: [universality_automata]
-Aliases: CFG universality, context free grammar universality, universality CFG
+Aliases: CFG universality, context free grammar universality, universality CFG, universality problem CFG, universality problem CFGs
