commit 7623417f24b32a46afd7d315d40ff706082e6c2e
parent 32ddbec5e6f091a4e390719ee346ff9148656700
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 14 Feb 2025 18:24:15 +0100
commit with codex
Diffstat:
6 files changed, 16 insertions(+), 19 deletions(-)
diff --git a/automaton_equivalence b/automaton_equivalence
@@ -1,8 +1,9 @@
# Automaton equivalence
-[pspace_complete] on [automata_nondeterministic]
-
-[ptime] on [automata_deterministic] via [product_construction]
+- [pspace_complete] on [automata_nondeterministic]
+- [ptime] on [automata_deterministic] via [product_construction]
+- [automaton_equivalence_pushdown_automaton]
+- [automaton_equivalence_pushdown_automaton_deterministic]
Up: [automata_problems]
diff --git a/complexity_class b/complexity_class
@@ -5,21 +5,8 @@
- [complexity_space]
- [nlogspace]
- [logspace]
-- [complexity_time]
- - [ptime] / [p_complete]
- - [linear_time], [linear_time_nearly], [linear_time_almost]
- - [np_intermediate], cf [ladners_theorem]
- - [nptime]
- - [conptime]
- - [np_cap_conp]
- - [exptime]
- - [nexptime]
- - [spanl]
- - [pp]
- - [pspace]
- - [pspace_complete]
- - [oplusp] oplusP
- - [us] US
+- [complexity_time]: [complexity_time_classes]
+- [spanl]
## [complexity_hierarchy]
diff --git a/complexity_time b/complexity_time
@@ -2,6 +2,8 @@
The [asymptotic] running time of an [algorithm]
+- [complexity_time_classes]
+
Up: [complexity_measure]
See also: [complexity_space]
diff --git a/pushdown_automaton b/pushdown_automaton
@@ -8,6 +8,10 @@
- introduced in [ginsburg1966finite]
- mentioned in [ganardi2018sliding]
+- [universality_automata_pushdown]
+
Up: [stack_automata]
See also: [visibly_pushdown_automaton]
+
+Aliases: pushdown automata
diff --git a/universality_automata b/universality_automata
@@ -4,6 +4,7 @@
- [universality_automata_nondeterministic]: [conp_complete]
- [universality_automata_deterministic]: [ptime]
+- [universality_automata_pushdown]
- [factor_universal]
- [subword_universal]
diff --git a/universality_automata_deterministic b/universality_automata_deterministic
@@ -1,6 +1,8 @@
# Universality automata deterministic
-in [ptime] via [automaton_complementation]
+In [ptime] via [automaton_complementation]
+
+Generalizes to [universality_automata_pushdown_deterministic]
Up: [universality_automata], [automaton_deterministic]
