commit 398534b3fc79b1581cd979816e757e6c3d2caa6c
parent 1594e9ffbff229de9af424942bd1a605fd7c8937
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 10 Dec 2025 12:07:09 +0100
commit with codex
Diffstat:
6 files changed, 37 insertions(+), 3 deletions(-)
diff --git a/automaton_inclusion b/automaton_inclusion
@@ -2,8 +2,9 @@
- [NFA_inclusion]: [PSPACE_complete]
- [UFA_inclusion]: [PTIME] by reduction to [UFA_universality]
- - by reduction to [NXA_universality]: https://cstheory.stackexchange.com/a/25478
-- [k_unambiguous_inclusion]: PTIME via [stearns1985equivalence]
+ - by reduction to [NXA_universality]:
+ - cf https://cstheory.stackexchange.com/a/25478
+- [k_unambiguous_inclusion]
- [DFA_inclusion]: [PTIME] via [product_construction]
[inclusion_DFA_trick]
@@ -14,6 +15,6 @@ Special case: [automaton_universality]
Up: [automata_problems], [language_inclusion]
-See also: [automaton_equivalence]
+See also: [automaton_equivalence], [automaton_universality]
Aliases: regular language inclusion
diff --git a/betweenness b/betweenness
@@ -0,0 +1,7 @@
+# Betweenness
+
+Given a set of ordered triples (a, b, c) on an ordered domain, decide if there is a total order < such that a < b < c or c < b < a
+
+[NP_hard], mentioned in [duprelatour2025hardness]
+
+Up: [decision_problem]
diff --git a/k_ambiguous_nfa b/k_ambiguous_nfa
@@ -6,4 +6,11 @@ For k=1, we get the notion of [UFAs]
[Counting_problem] on [density_function] (number of accepted [words]): [sharp_k_UFA]
+- [k_unambiguous_universality]
+- [k_unambiguous_inclusion]
+
Up: [k_ambiguous], [NFA]
+
+Aliases: k unambiguous NFA
+
+See also: [word_automaton_k_unambiguous]
diff --git a/k_unambiguous_inclusion b/k_unambiguous_inclusion
@@ -0,0 +1,9 @@
+# K unambiguous inclusion
+
+[PTIME] via [stearns1985equivalence]
+
+see also https://cstheory.stackexchange.com/a/25478
+
+Up: [automaton_inclusion], [k_unambiguous_word_automaton]
+
+See also: [k_unambiguous_universality]
diff --git a/k_unambiguous_universality b/k_unambiguous_universality
@@ -0,0 +1,9 @@
+# K unambiguous universality
+
+[PTIME], cf https://cstheory.stackexchange.com/a/25478 and https://games-automata-play.github.io/blog/universality_finitely_ambiguous/
+
+Up: [k_ambiguous_nfa], [automaton_universality]
+
+Aliases: universality k unambiguous, universality k ambiguous
+
+See also: [K_unambiguous_inclusion], [K_unambiguous_equivalence]
diff --git a/universality_automata b/universality_automata
@@ -5,6 +5,7 @@ The [computational_problem] of testing if an [automaton] accepts every possible
- [universality_automata_nondeterministic]: [coNP_complete]
- [universality_automata_upwards_closed]
- [universality_automata_downwards_closed]
+ - [universality_k_unambiguous]
- [universality_automata_deterministic]: [ptime]
- [universality_context_free_grammar]
- [universality_automata_pushdown]
