wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

commit 6c13a9ca0a68ed6263c66cd8cbc940459ad43e56
parent cf818e2b20cc7577655eeeb7cfddab8d6764b957
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 29 Jul 2025 15:41:30 +0200

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
co_lexicographic_order | 2+-
computational_complexity | 3++-
limited_automata | 9+++++++++
theorem | 1+
turing_machine | 1+
5 files changed, 14 insertions(+), 2 deletions(-)

diff --git a/co_lexicographic_order b/co_lexicographic_order @@ -2,6 +2,6 @@ defined in [cotumaccio2023colexicographically] -See also: [lexicographic_order], [cotumaccio2024myhill] +See also: [lexicographic_order], [cotumaccio2024myhill], [Wheeler_NFA] Up: [order] diff --git a/computational_complexity b/computational_complexity @@ -40,7 +40,7 @@ ## Results - [ladners_theorem] -- [complexity_zoo] +- [Rice's_theorem] ## Techniques @@ -52,6 +52,7 @@ - [descriptive_complexity] - [lower_bounds] - [klees_measure_problem] +- [complexity_zoo] Up: [theoretical_computer_science], [complexity] diff --git a/limited_automata b/limited_automata @@ -0,0 +1,9 @@ +# Limited automata + +[survey_paper]: [pighizzini2019limited] + +Used in [guillon2025polynomial] + +Up: [automata_types] + +Aliases: automaton limited, automata limited, limited automaton diff --git a/theorem b/theorem @@ -28,6 +28,7 @@ A [result] in [mathematics], recognized as challenging to prove - [Parikh's_theorem] - [Prime_number_theorem] - [Ramsey_theorem] +- [Rice's_theorem] - [Roths_theorem] - [Savitch's_theorem] - [Schnyder's_theorem] diff --git a/turing_machine b/turing_machine @@ -15,6 +15,7 @@ - [turing_machine_symmetric] - [turing_machine_weighted] +- [turing_machine_multitape] ## Resources