universality_automata (806B)
1 # Automaton universality 2 3 The [computational_problem] of testing if an [automaton] accepts every possible [word] 4 5 - [universality_automata_nondeterministic]: [coNP_complete] 6 - [universality_automata_upwards_closed] 7 - [universality_automata_downwards_closed] 8 - [universality_k_unambiguous] 9 - [universality_automata_deterministic]: [ptime] 10 - [universality_context_free_grammar] 11 - [universality_automata_pushdown] 12 13 - [factor_universal] 14 - [subword_universal] 15 16 Variant: [length_universality_automata] 17 18 Generalization: [automaton_inclusion], [automaton_equivalence] 19 20 Up: [universality_problem], [automata_problems] 21 22 See also: [totality], [validity], [taulology], [automaton_emptiness] 23 24 Aliases: automata universality, automaton universality, universality automata problem, automaton universality problem