commit 42afe5cfaaf51d1e27f98ce8a6414871426af90a
parent 57aab99f0ba9ad5fd4b770e9777040084f2905fe
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 27 Oct 2025 16:28:42 +0100
commit with codex
Diffstat:
17 files changed, 91 insertions(+), 10 deletions(-)
diff --git a/automaton_equivalence b/automaton_equivalence
@@ -1,7 +1,7 @@
# Automaton equivalence
-- [pspace_complete] on [automata_nondeterministic]
-- [ptime] on [automata_deterministic] via [product_construction]
+- [NFA_equivalence]: [pspace_complete]
+- [DFA_equivalence]: [ptime] via [product_construction]
- [automaton_equivalence_pushdown_automaton]
- [automaton_equivalence_pushdown_automaton_deterministic]
diff --git a/automaton_inclusion b/automaton_inclusion
@@ -1,8 +1,7 @@
# Automaton inclusion
-[PSPACE_complete] for [nondeterministic_automata]
-
-[PTIME] for [automata_deterministic]
+- [NFA_inclusion]: [PSPACE_complete]
+- [DFA_inclusion]: [PTIME] via [product_construction]
Up: [automata_problems], [language_inclusion]
diff --git a/context_free_grammar b/context_free_grammar
@@ -54,6 +54,7 @@
## Results
- [Greibach's_theorem]
+- [Chomsky-Schützenberger_theorem]
See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar]
diff --git a/description_logics b/description_logics
@@ -14,3 +14,5 @@ Topics:
Up: [logic]
See also: [FO2], [Guarded_Fragment]
+
+Aliases: description logic
diff --git a/dfa_equivalence b/dfa_equivalence
@@ -0,0 +1,7 @@
+# DFA equivalence
+
+[ptime] via [product_construction]
+
+Up: [automaton_equivalence] on [DFAs]
+
+See also: [DFA_inclusion], [NFA_equivalence]
diff --git a/dfa_inclusion b/dfa_inclusion
@@ -0,0 +1,7 @@
+# DFA inclusion
+
+in [PTIME] via [product_construction]
+
+Up: [automaton_inclusion] for [DFAs]
+
+See also: [DFA_equivalence], [NFA_inclusion]
diff --git a/formal_language b/formal_language
@@ -14,6 +14,7 @@ A [set] of [words] over an [alphabet]
- [slice]: [subset] of the [words] of a certain [length]
- [density_function]
- [language_unary]
+- [formal_language_primality]
- [computational_problems]: [formal_language_computational_problems]
diff --git a/greibachs_theorem b/greibachs_theorem
@@ -0,0 +1,11 @@
+# Greibach's theorem
+
+https://en.wikipedia.org/wiki/Greibach%27s_theorem
+
+Can be used to show that deciding whether a [CFG] recognizes a [regular_language], or a [linear_CFL], is [undecidable]
+- cf article [greibach1968note]
+- cf https://cstheory.stackexchange.com/q/55586
+
+Up: [context_free_grammar]
+
+See also: [Rice's_theorem], [bodirdski2024hereditary]
diff --git a/matching b/matching
@@ -24,3 +24,5 @@ Also the [linear_relaxation]: see [fractional_edge_packing]
See also: [independent_set], [induced_matching], [graph_matching_covered], [deficiency]
Up: [graph_substructure]
+
+Aliases: matchings
diff --git a/nfa_equivalence b/nfa_equivalence
@@ -0,0 +1,7 @@
+# NFA equivalence
+
+[PSPACE_complete]
+
+Up: [automaton_equivalence] on [NFAs]
+
+See also: [NFA_inclusion], [DFA_equivalence]
diff --git a/nfa_inclusion b/nfa_inclusion
@@ -0,0 +1,7 @@
+# NFA inclusion
+
+[PSPACE_complete]
+
+Up: [automaton_inclusion] for [NFAs]
+
+See also: [NFA_equivalence], [DFA_inclusion]
diff --git a/open_world_query_answering b/open_world_query_answering
@@ -1,7 +1,28 @@
# Open world query answering
-Given a [database], [database_dependency] or [ontology], and [query], check if
-it implied
+This gets its name from the [open_world_semantics], which is that of databases
+which may be missing some information. (Think of a [knowledge_base], like
+[Wikidata]: you can hope that the facts of Wikidata are true, but there are
+some true facts that are not in Wikidata.) You may have some integrity
+constraints and reasoning rules (e.g., father(x,y) -> parent(x,y), or
+locatedIn(x,y) locatedIn(y,z) -> locatedIn(x,z)) and the database doesn't
+necessarily satisfy these constraints directly (e.g., some of the entailed
+facts may not be materialized in the data)
+
+Formally, you have a [database] D, a set of database constraints Σ (e.g.,
+[database_dependencies], [integrity_constraints], an [ontology], etc.), and a
+query Q. You want to consider all possible completions D' of D (i.e., D
+subseteq D') subject to the constraints (i.e., D' \models Σ) and you want to
+know whether all of these completions satisfy the query Q. (So that Q is not
+necessarily true on D but is "entailed" in the sense that every completion of
+D satisfying Σ must satisfy Q -- note that Q is typically monotone.) The
+negation of the problem asks whether there is a counterexample model, i.e., a
+completion D' of D that satisfies Σ but not Q (equivalently, that satisfies Σ
+\land \neg Q). So this is the question of asking whether a superset of some
+extensional data satisfies a logical formula (of a somewhat weird kind --
+typically Σ would consist of [tuple_generating_dependencies],
+[existential_rules], or [description_logic] rules, whereas \neg Q would be the
+negation of a [conjunctive_query] or [union_of_conjunctive_queries]).
Also called "ontology-based data access", see also [ontology_mediated_query]
@@ -12,9 +33,12 @@ Also called "ontology-based data access", see also [ontology_mediated_query]
By [constraint_language]:
- [open_world_query_answering_fds]
-
- [open_world_query_answering_rpqs]
+Related to [query_containment]
+
+References: [imielinski1984incomplete], [arenas1999consistent], [cali2003decidability], [xiao2018ontology]
+
See also: [query_evaluation], [satisfiability], [open_world_semantics]
Up: [database_theory]
diff --git a/primitive_word_language b/primitive_word_language
@@ -10,6 +10,6 @@ Discussed in [lischke2011primitive]
Up: [formal_language], [primitive_word]
-See also: [square_language], [composite_word_language]
+See also: [square_language], [composite_word_language], [formal_language_primality]
Aliases: primitive words language
diff --git a/regular_language b/regular_language
@@ -34,6 +34,8 @@
- connection to [cycle_rank] of [automata] via [eggans_theorem]
- [generalized_star_height] en ajoutant [complementation]
- generalized star height of zero is [star_free_language]
+- [state_complexity]
+- [syntactic_complexity]
## Results
diff --git a/sharpp_hard b/sharpp_hard
@@ -3,3 +3,5 @@
depends on the notion of [reduction]: [sharpP_Hard_reductions]
Up: [hardness] for [sharpp]
+
+Aliases: sharpP_hardness
diff --git a/syntactic_complexity b/syntactic_complexity
@@ -0,0 +1,9 @@
+# Syntactic complexity
+
+The cardinality of the [syntactic_semigroup] of a [regular_language]
+
+Studied for instance in [brzozowski2012syntactic]
+
+Up: [regular_language]
+
+See also: [state_complexity]
diff --git a/tuple_generating_dependency b/tuple_generating_dependency
@@ -36,4 +36,4 @@ Up: [database_dependency]
See also: [datalogpm], [denial_constraint]
-Aliases: TGD, TGDs
+Aliases: TGD, TGDs, tuple generating dependencies
