commit 46cd9cd64424192521734656b300c20ce055d3e6
parent a7bc0a624d3a07d99c05ff8f4c9b0d9f39576fef
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 2 Sep 2025 10:47:37 +0200
commit with codex
Diffstat:
2 files changed, 4 insertions(+), 3 deletions(-)
diff --git a/sharp_automaton b/sharp_automaton
@@ -4,6 +4,7 @@
- [sharp_nfa]
- [sharp_ufa]
+ - [sharp_ufa_tree]
- [sharp_dfa]
Up: [counting_problem], [automata]
diff --git a/sharp_ufa b/sharp_ufa
@@ -1,12 +1,12 @@
# Sharp-UFA
-given [word_automaton_unambiguous] A and length n in [unary], count the number of words of length n accepted by A
+given an [unambiguous_word_automaton] A and length n written in [unary], count the number of words of length n accepted by A
-in [ptime], by counting [runs]
+This is in [ptime], by counting [runs]
even if n is given in binary, by [fast_exponentiation] and [matrix_multiplication]
- cf https://cstheory.stackexchange.com/a/8202
Up: [sharp_automaton], [word_automaton_unambiguous]
-See also: [sharp_nfa], [sharp_dfa], [density_function]
+See also: [sharp_nfa], [sharp_dfa], [density_function], [sharp_ufa_tree]
