wiki_research

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

commit b9b4409ef4d377b0cc3a0f79d8a826c6a7d9cf70
parent 304bad0e0f536d5b1cd2c9c81dfc77cc942de11a
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Fri,  6 Jun 2025 16:17:12 +0200

commit with codex

Diffstat:
bagan2020trichotomy | 18------------------
minimal_witness | 2++
2 files changed, 2 insertions(+), 18 deletions(-)

diff --git a/bagan2020trichotomy b/bagan2020trichotomy @@ -1,18 +0,0 @@ -# bagan2020trichotomy - -Article showing [simple_path_trichotomy] - -## Intuition of criterion - -"term" = (w+eps) or (A^{\geq k} + eps) - with w a fixed word, and A some subalphabet -"sequence": concatenation of terms, with fixed words before and after - -tractable class: disjunction of sequences - -tractability is not obvious! intuitively we can "shorten" thanks to the +epsilon - -equivalent reformulation: "closed under skipping" -=> [algebraic_automata_theory] characterization? cf [martens2023trichotomy] in the case of [trail_trichotomy] - -Up: [academic_paper_list] diff --git a/minimal_witness b/minimal_witness @@ -14,3 +14,5 @@ easy for [conjunctive_query_full], so hardness comes from [projection] Up: [database_theory] See also: [query_resilience], [smallest_synthetic_witness], [synthetic_witness] + +Aliases: minimum witness, smallest witness