commit ebb763e1ebea2be20b438edafba6e64b1fa7e59b
parent c185c37c66546c01ad2673459b935ed1b26c9a61
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 1 Dec 2025 13:41:28 +0100
commit with codex
Diffstat:
19 files changed, 133 insertions(+), 14 deletions(-)
diff --git a/automaton_downwards_closed b/automaton_downwards_closed
@@ -0,0 +1,19 @@
+# Downwards closed automaton
+
+Deciding if the language of an [NFA] is [language_downwards_closed] is [PSPACE_complete] even on an alphabet of size 2, cf [karandikar2016deciding] Proposition 7.1. But it is [NL_complete] on [DFAs]
+
+Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite]
+
+Ditto for [automaton_inclusion], cf [karandikar2016state] Proposition 7.3
+
+[automaton_inclusion_downwards_closed]
+
+All of this holds even if only the right-hand-side [NFA] is upwards-closed, cf also [inclusion_DFA_trick]
+
+[universality_automaton_downwards_closed]
+
+See also: [automaton_upwards_closed]
+
+Up: [language_downwards_closed]
+
+Aliases: downwards closed automaton, downwards closed automata, subword closed automaton, subword closed automata, automaton subword closed, subsequence closed automaton, subsequence closed automaton, automaton subsequence closed, automata subsequence closed
diff --git a/automaton_inclusion_downwards_closed b/automaton_inclusion_downwards_closed
@@ -0,0 +1,9 @@
+# Automaton inclusion downwards closed
+
+Testing [automaton_inclusion] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [karandikar2016state] Proposition 7.3
+
+All of this holds even if only the right-hand-side [NFA] is upwards-closed, cf also [inclusion_DFA_trick]
+
+Up: [automaton_inclusion], [automaton_downwards_closed]
+
+See also: [automaton_inclusion_upwards_closed]
diff --git a/automaton_inclusion_upwards_closed b/automaton_inclusion_upwards_closed
@@ -0,0 +1,9 @@
+# Automaton inclusion upwards closed
+
+Testing [automaton_inclusion] on two [NFAs] recognizing upwards closed languages is [coNP_complete], cf [karandikar2016state] Proposition 7.3
+
+All of this holds even if only the right-hand-side [NFA] is upwards-closed, cf also [inclusion_DFA_trick]
+
+Up: [automaton_inclusion], [automaton_upwards_closed]
+
+See also: [Automaton_inclusion_downwards_closed]
diff --git a/automaton_upwards_closed b/automaton_upwards_closed
@@ -0,0 +1,19 @@
+# Upwards closed automaton
+
+Deciding if the language of an [NFA] is [language_upwards_closed] is [PSPACE_complete] even on an alphabet of size 2, cf [karandikar2016deciding] Proposition 7.1. But it is [NL_complete] on [DFAs]
+
+Testing the [automaton_equivalence] of two [NFAs] recognizing upwards closed languages is [coNP_complete], cf [bachmeier2014finite]
+
+[automaton_inclusion_upwards_closed]
+
+Ditto for [automaton_inclusion], cf [karandikar2016state] Proposition 7.3
+
+All of this holds even if only the right-hand-side [NFA] is upwards-closed, cf also [inclusion_DFA_trick]
+
+[universality_automaton_upwards_closed]
+
+Up: [language_upwards_closed]
+
+Aliases: upwards closed automaton, Upwards closed automata, automaton subword closed, subword closed automaton, subword closed automata, supersequence closed automaton, supersequence closed automata, automata supersequence closed, automaton supersequence closed
+
+See also: [downwards_closed_automaton]
diff --git a/crossing_number b/crossing_number
@@ -8,4 +8,8 @@ An [undirected_graph] is a [planar_graph] iff the crossing number is zero
[crossing_number_inequality]
+The crossing number of [complete_bipartite_graphs] is an [open_problem], cf https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_brick_factory_problem
+
Up: [planar_graph]
+
+See also: [single_crossing_graph]
diff --git a/disjoint_path_2 b/disjoint_path_2
@@ -10,6 +10,6 @@ Not to be confused with the problem of finding two vertex-disjoint paths from {s
Up: [disjoint_paths]
-See also: [edge_connectedness], [simple_path_RPQ]
+See also: [edge_connectedness], [simple_path_RPQ], [even_path_problem]
-Aliases: two disjoint path problem, two disjoint paths, Disjoint path 2, twodisjoint path problem, two disjoint simple path, two disjoint simple paths, two disjoint simple path problem, two disjoint simple paths problem
+Aliases: two disjoint path problem, two disjoint paths, Disjoint path 2, twodisjoint path problem, two disjoint simple path, two disjoint simple paths, two disjoint simple path problem, two disjoint simple paths problem, 2 disjoint path problem, 2 disjoint paths problem
diff --git a/even_cycle b/even_cycle
@@ -6,4 +6,4 @@ An *even cycle* is a [cycle] whose [length] is [even]
Up: [cycle]
-See also: [odd_cycle]
+See also: [odd_cycle], [even_path]
diff --git a/even_path b/even_path
@@ -0,0 +1,9 @@
+# Even path
+
+An *even path* is a [path] whose length is [even]
+
+- [even_path_problem]
+
+See also: [even_cycle]
+
+Up: [path], [even]
diff --git a/even_path_problem b/even_path_problem
@@ -0,0 +1,13 @@
+# Even path problem
+
+The [decision_problem] of whether a [directed_graph] has an [even_path] from s to t
+
+It is easy for [walks] but [NP_hard] for [simple_paths] by reduction from [2_disjoint_paths_problem], cf [lapaugh1984even]
+
+Tractable for [directed_single_crossing_graphs], cf [chauhuan2025evenpath]
+
+Discussed in [amarilli2024survey]
+
+Up: [decision_problem], [even_path]
+
+See also: [even_cycle_problem]
diff --git a/language_downwards_closed b/language_downwards_closed
@@ -1,6 +1,6 @@
# Language downwards closed
-A [formal_language] is *downwards closed* if any [subword] of the [formal_language] is in the [formal_language]
+A [formal_language] is *downwards closed* if any [subsequence] of a [word] of the [formal_language] is in the [formal_language]
[ideal_decomposition]: every downward closed language is a finite [union] of [language_ideal] i.e. terms of the form
@@ -11,10 +11,8 @@ A [formal_language] is *downwards closed* if any [subword] of the [formal_langua
The [language_complement] of a downwards closed [formal_language] is a [upwards_closed_language].
-Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite]
-
Up: [regular_language_family]
-See also: [higmans_lemma], [downwards_closure], [language_factor_minimal], [language_upwards_closed], [ganardi2024directed]
+See also: [higmans_lemma], [downwards_closure], [language_factor_minimal], [language_upwards_closed], [ganardi2024directed], [automaton_upwards_closed]
Aliases: downward closed language, downward closed languages, downwards closed language, downwards closed languages
diff --git a/language_upwards_closed b/language_upwards_closed
@@ -1,6 +1,6 @@
# Language upwards closed
-A [formal_language] is *upwards closed* if any [subword] of the [formal_language] is in the [formal_language]
+A [formal_language] is *upwards closed* if any [supersequence] of a [word] of the [formal_language] is in the [formal_language]
The [language_complement] of an upwards closed [formal_language] is a [downwards_closed_language].
@@ -8,6 +8,6 @@ Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed l
Up: [regular_language_family]
-See also: [higmans_lemma], [upwards_closure], [language_factor_minimal], [language_downwards_closed]
+See also: [higmans_lemma], [upwards_closure], [language_factor_minimal], [language_downwards_closed], [automaton_upwards_closed]
Aliases: upward closed language, upward closed languages, upwards closed language, upwards closed languages
diff --git a/planar_graph b/planar_graph
@@ -1,6 +1,6 @@
# Planar graph
-A [graph_undirected] that has a [plane_embedding], i.e., can be embedded on [plane_mathematics]
+A [graph_undirected] that has a [plane_embedding], i.e., can be embedded on [plane_mathematics], without [edges] that cross
- Recognizing them: [planarity_testing]
- [dynamic_planarity_testing]
@@ -32,6 +32,7 @@ Generalizations:
- to [hypergraphs]: [planar_hypergraph]
- to [directed_graphs]: [directed_planar_graph]
- to quantify the "degree of non-planarity": [crossing_number]
+- [single_crossing_graph]
See also: [graph_drawing], [planar_separator_theorem]
diff --git a/pseudoforest b/pseudoforest
@@ -4,6 +4,8 @@ https://en.m.wikipedia.org/wiki/Pseudoforest
[Undirected_graph] in which every [connected_component] has at most one [cycle]
+[Directed_graph] version: https://en.wikipedia.org/wiki/Pseudoforest#Directed_pseudoforests
+
Up: [forest]
Aliases: pseudoforests
diff --git a/simple_path_parity_problem b/simple_path_parity_problem
@@ -1,6 +1,6 @@
# Simple path parity problem
-[Computational_problem] of deciding if there is a [simple_path] in a [graph] from a vertex s to a vertex t that has even length (or odd length)
+[Computational_problem] of deciding if there is a [simple_path] in a [directed_graph] from a vertex s to a vertex t that has even length (or odd length)
This is [NP_complete] in general graphs by reduction from [two_disjoint_simple_path]
diff --git a/simple_path_rpq_problem b/simple_path_rpq_problem
@@ -8,4 +8,4 @@ Also [enumeration]: [simple_path_rpq_enumeration]
Up: [simple_path_problem], [RPQ]
-See also: [simple_path_modulo]
+See also: [simple_path_modulo], [simple_path_RPQ_planar]
diff --git a/single_crossing_graph b/single_crossing_graph
@@ -0,0 +1,16 @@
+# Single crossing graph
+
+discussed in https://cstheory.stackexchange.com/questions/50303/finding-the-single-crossing-embedding-of-a-single-crossing-graph/50306
+
+A [graph] that has a [planar_embedding] where only one pair of [edges] cross
+
+Types:
+
+- [single_crossing_graph_undirected]
+- [single_crossing_graph_directed]
+
+Up: [planar_graph]
+
+See also: [crossing_number]
+
+Aliases: single crossing graphs
diff --git a/universality_automata b/universality_automata
@@ -2,7 +2,9 @@
The [computational_problem] of testing if an [automaton] accepts every possible [word]
-- [universality_automata_nondeterministic]: [conp_complete]
+- [universality_automata_nondeterministic]: [coNP_complete]
+ - [universality_automata_upwards_closed]
+ - [universality_automata_downwards_closed]
- [universality_automata_deterministic]: [ptime]
- [universality_context_free_grammar]
- [universality_automata_pushdown]
@@ -18,4 +20,4 @@ Up: [universality_problem], [automata_problems]
See also: [totality], [validity], [taulology], [automaton_emptiness]
-Aliases: automata universality, automaton universality
+Aliases: automata universality, automaton universality, universality automata problem, automaton universality problem
diff --git a/universality_automaton_downwards_closed b/universality_automaton_downwards_closed
@@ -0,0 +1,9 @@
+# Automaton universality for downwards closed automata
+
+The [automaton_universality_problem] for [downwards_closed_automata] is [NL_complete], you simply have to check if there is an [SCC] containing all letters, cf [karandikar2016state] Proposition 7.4
+
+Up: [automaton_universality_problem], [automaton_downwards_closed]
+
+See also: [automaton_universality_for_upwards_closed_automata]
+
+Aliases: automaton universality for downwards closed automata
diff --git a/universality_automaton_upwards_closed b/universality_automaton_upwards_closed
@@ -0,0 +1,9 @@
+# Automaton universality for upwards closed automata
+
+The [automaton_universality_problem] for [upwards_closed_automata] is trivial, you simply have to check if the [empty_word] is accepted.
+
+Up: [automaton_universality_problem], [automaton_upwards_closed]
+
+Aliases: Automaton universality for upwards closed automata
+
+See also: [automaton_universality_for_downwards_closed_automata]
