New answers tagged dfa
4
I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states.
An exponential lower bound on $f$ can be given as follows.
Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that ...
Top 50 recent answers are included
Related Tags
dfa × 54automata-theory × 35
fl.formal-languages × 13
regular-language × 12
reference-request × 8
regular-expressions × 8
cc.complexity-theory × 6
nfa × 6
graph-theory × 5
ds.algorithms × 3
lg.learning × 3
time-complexity × 2
graph-isomorphism × 2
space-bounded × 2
open-problem × 2
nondeterminism × 2
finite-model-theory × 2
homomorphism × 2
graph-algorithms × 1
co.combinatorics × 1
soft-question × 1
optimization × 1
machine-learning × 1
big-picture × 1
tree × 1