commit 44dc711c1df541421cb188890ff058efa6c77829
parent 44985f3777147acca1d6ecb5e2e6dafd58b80f0a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 15 Nov 2025 09:58:25 +0100
commit with codex
Diffstat:
8 files changed, 33 insertions(+), 3 deletions(-)
diff --git a/description_logics b/description_logics
@@ -6,6 +6,11 @@ A set of lightweight [logics] with different complexity depending on the feature
Classes:
- [DL-Lite]
+- [ALC]
+ - conjunctions imply disjunctions
+ - can use existentials in [rule_head] and [rule_body]
+ - can use true and [bottom]
+- [transitivity_assertions]
Topics:
- [Description_logics_descriptive_complexity]
diff --git a/e b/e
@@ -0,0 +1,7 @@
+# E
+
+Like [EXPTIME] but with a linear exponent; cf [bodirsky2025computational]
+
+Nondeterministic version: [NE]
+
+Up: [exptime]
diff --git a/existential_second_order_logic b/existential_second_order_logic
@@ -7,3 +7,5 @@ Corresponds to [NP] by [Fagin's_theorem]
Up: [second_order_logic]
Aliases: existential SO, ESO
+
+See also: [universal_second_order_logic]
diff --git a/exptime b/exptime
@@ -4,6 +4,8 @@ https://en.wikipedia.org/wiki/EXPTIME
in 2^{P(n)} for P a [polynomial]
+- [E]: in 2^{O(n)}
+
Up: [complexity_time_classes]
See also: [2exptime], [EXPTIME_complete], [nexptime]
diff --git a/open_world_query_answering b/open_world_query_answering
@@ -42,3 +42,5 @@ References: [imielinski1984incomplete], [arenas1999consistent], [cali2003decidab
See also: [query_evaluation], [satisfiability], [open_world_semantics]
Up: [database_theory]
+
+Aliases: OWQA
diff --git a/second_order_logic b/second_order_logic
@@ -1,13 +1,21 @@
# SO
+[descriptive_complexity]: corresponds to the [polynomial_hierarchy]
+
+Restrictions:
+
+- [existential_second_order_logic] corresponds to [NP] by [Fagin's_theorem]
+- [universal_second_order_logic] corresponds to [coNP]
+- [quantifier_prefix]
- [monadic_second_order_logic]
-- [descriptive_complexity]: correspondence with [polynomial_hierarchy]
- - [existential_second_order_logic] corresponds to [NP] by [Fagin's_theorem], etc.,
- [quantifier_prefix]
+
+Extensions:
+
- [second_order_transitive_closure] SO(TC) [ferrarotti2018expressivity]
- corresponds to [pspace]
- can express [hamiltonian_cycle]
- which is known not to be expressible in [monadic_second_order_logic]
+ - restrictions: [monadic_second_order_logic_transitive_closure] MSO(TC)
See also: [first_order_logic]
diff --git a/transitivity b/transitivity
@@ -2,6 +2,8 @@
- [transitivity_tgds]
- [transitive_closure]
+- [transitivity_assertion]
+- [transitive_relation]
Up: [mathematics]
diff --git a/vertex_deletion b/vertex_deletion
@@ -2,6 +2,8 @@
Removing a [vertex] from a [graph], and doing [edge_removal] of all [edges] that are [incident] to the removed [vertex]
+Computational hardness: [yannakakis1978node]
+
Up: [graph_modification]
Aliases: vertex removal
