unambiguity (1187B)
1 # Unambiguity 2 3 An [automata] is [unambiguous] if every word that it accepts has at most one accepting run. In particular see [word_automaton_unambiguous] 4 5 ## Generalization 6 7 - [k_ambiguous] [automata] 8 - comparison between different types of ambiguity: [ravikumar1989relating] 9 - [unambiguity_alternating] 10 11 ## Variants 12 13 - "strongly unambiguous" automaton: an automaton that can be used both an as unambiguous automaton for the language and as an unambiguous automaton for the [complement]: defined in [colcombet2012forms] 14 15 ## Separation 16 17 - Exponential separation between unambiguous automaton and [automata_nondeterministic]: section 3 of [leung2005descriptional] ([communication_complexity] method) 18 19 pas de conversion polynomiale de 2-UFA vers [unambiguous_finite_automaton] par [goos2021lower] 20 - mais on peut compter les mots acceptés par un k-UFA à k constant par 21 [stearns1985equivalence] 22 23 ## Types 24 25 - [unambiguous_star_free_language] 26 27 ## For [context_free_language] 28 29 - [context_free_grammar_unambiguous] 30 31 ## For other problems 32 33 - [satisfiability_unambiguous] 34 35 See also: [ddnnf], [unambiguous], [determinism_language] 36 37 Up: [formal_language_theory] 38 39 Aliases: automaton unambiguous