commit d1382dba00a77e1fbe999663313c31257240cc27
parent ea0accc24cc2fd85ae66b140bcb8a940a6477bdd
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 20 Mar 2025 17:23:39 +0100
commit with codex
Diffstat:
4 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/degree_of_ambiguity b/degree_of_ambiguity
@@ -0,0 +1,13 @@
+# Degree of ambiguity
+
+[asymptotic] number of [accepting_runs] of a [nondeterministic_automaton]
+
+- [degree_of_ambiguity_nfa]
+ - [degree_of_ambiguity_tree_automata]
+- [degree_of_ambiguity_cfg]
+
+- [polynomial_ambiguity]
+
+Up: [nondeterministic]
+
+See also: [density_function], [k_ambiguous_ddnnf]
diff --git a/degree_of_ambiguity_tree_automata b/degree_of_ambiguity_tree_automata
@@ -0,0 +1,5 @@
+# Degree of ambiguity tree automata
+
+[gallot2025structure]
+
+Up: [degree_of_ambiguity], [tree_automaton]
diff --git a/tree_automaton b/tree_automaton
@@ -6,6 +6,8 @@ Defines [regular_tree_language]
- [tree_automaton_bottom_up]
- [tree_automaton_top_down]
+- [tree_automaton_deterministic]
+- [tree_automaton_nondeterministic]
## Variants
diff --git a/tree_automaton_nondeterministic b/tree_automaton_nondeterministic
@@ -0,0 +1,9 @@
+# Tree automaton nondeterministic
+
+Can be [bNTA] or [tNTA]: same expressive power, and actually no difference in formalisms
+
+Up: [tree_automaton], [nondeterministic]
+
+See also: [tree_automaton_deterministic]
+
+Aliases: nondeterministic tree automaton, nondeterministic tree automata
