3-Party Message Complexity is Better than 2-Party Ones for Proving Lower Bounds on the Size of Minimal Nondeterministic Finite Automata.
Henry N. AdornaPublished in: DCFS (2001)
Keyphrases
- finite automata
- lower bound
- regular expressions
- deterministic automata
- probabilistic automata
- grammatical inference
- upper bound
- worst case
- computational complexity
- space complexity
- memory requirements
- finite automaton
- tree automata
- multi party
- hidden markov models
- average case complexity
- objective function
- np hard
- database systems
- knowledge base