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