commit 879df527394727dc285bdb55e90f329b22acd597
parent 4b4e551904ea16c22591f27e88c07aa2c7596ad5
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 24 Feb 2026 23:59:10 +0100
commit with codex
Diffstat:
7 files changed, 13 insertions(+), 6 deletions(-)
diff --git a/context_free_grammar_inclusion b/context_free_grammar_inclusion
@@ -4,4 +4,6 @@ It is [undecidable], already for [uCFLs], and already for [linear_uCFLs], see [a
Up: [inclusion_problem], [context_free_grammar]
-Aliases: CFG inclusion
+Aliases: CFG inclusion, CFG language inclusion
+
+See also: [CFG_equivalence], [CFG_universality]
diff --git a/inclusion_dependency b/inclusion_dependency
@@ -3,3 +3,5 @@
- [inclusion_dependency_unary]
Up: [tuple_generating_dependency_linear]
+
+Aliases: inclusion dependencies
diff --git a/inclusion_dependency_unary b/inclusion_dependency_unary
@@ -4,6 +4,6 @@
Up: [inclusion_dependency]
-Aliases: UID, UIDs, unary ID, unary IDs, unary inclusion dependency
+Aliases: UID, UIDs, unary ID, unary IDs, unary inclusion dependency, unary inclusion dependencies
See also: [functional_dependency_unary]
diff --git a/k_relation b/k_relation
@@ -6,6 +6,7 @@ Used in:
- [hannula2024conditional] which uses [atserias2020consistency]
- [atserias2023consistency]
+- [hannula2026dichotomy] for [dependency_axiomatization] of [inclusion_dependencies]
Up: [relation] with [semiring]
diff --git a/universality_automata b/universality_automata
@@ -2,7 +2,8 @@
The [computational_problem] of testing if an [automaton] accepts every possible [word]
-- [universality_automata_nondeterministic]: [coNP_complete]
+- [universality_automata_nondeterministic]:
+ - [PSPACE_complete], and [coNP_complete] for [unary_alphabet]
- [universality_automata_upwards_closed]
- [universality_automata_downwards_closed]
- [universality_k_unambiguous]
diff --git a/universality_automata_nondeterministic b/universality_automata_nondeterministic
@@ -1,9 +1,10 @@
# Universality automata nondeterministic
-[conp_complete] even on [unary_alphabet]:
+[conp_complete] on [unary_alphabet] and [PSPACE_complete] otherwise:
- https://cs.stackexchange.com/a/97751
-The shortest rejected word of an automaton with O(n) states may be Omega(n 2^n): cf [ellul2005regular], Theorem 32
+The shortest rejected word of an [NFA] with O(n) states may be
+Omega(n 2^n): cf [ellul2005regular], Theorem 32
Up: [universality_automata], [automata_nondeterministic]
diff --git a/universality_context_free_grammar b/universality_context_free_grammar
@@ -7,6 +7,6 @@
Up: [universality_problem]
-See also: [universality_automata]
+See also: [universality_automata], [CFG_language_inclusion], [CFG_equivalence]
Aliases: CFG universality, context free grammar universality, universality CFG, universality problem CFG, universality problem CFGs
