8
$\begingroup$

I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ states) in software and operate with them. May someone suggest me data structures with reasonable performance and a good book with algorithms for automata theory (minimization, determinization, extraction of regular languages, automata equivalence, ...)?

PS: This is my first question and my English is very poor but I expect everyone to understand. Thanks in advance

|cite|improve this question
$\endgroup$
  • $\begingroup$ Twenty million? Hmm. How many symbols in your alphabet? $\endgroup$ – Chad Brewbaker Mar 14 '14 at 2:27
  • 1
    $\begingroup$ I think an open research question would be how to order the automata states in memory to optimize cache efficiency. For spatial graphs we can use Z curves, cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/papers/… $\endgroup$ – Chad Brewbaker Mar 14 '14 at 3:14
  • 3
    $\begingroup$ I don't necessarily agree with @Kaveh, and think this question could be a good fit here too, and I would wait for more opinions than just his. However, it would help if you made your question a bit more focused. What kind of finite automata are you working with? DFAs, NFAs, WAs, etc. What sort of tasks do you need to do with them? Assume that we know everything about finite automata but absolutely nothing about 'control engineering' or 'discrete event systems and supervisory control'. Based on this we can better judge if we can answer your question, or if it fits better elsewhere. $\endgroup$ – Artem Kaznatcheev♦ Mar 14 '14 at 3:41
  • 10
    $\begingroup$ The model-checking community uses BDDs a lot to represent automata, e.g. Symbolic model checking: $10^{20}$ states and beyond. $\endgroup$ – Sylvain Mar 14 '14 at 7:03
  • 4
    $\begingroup$ I would suggest having a look at how it is done in finite-state model checkers like SPIN. One question I have is whether you actually need some of the more costly operations (explicit product computation, determinization) - if your main question is (forward or backward) reachability, on-the-fly exploration of a system of NFA is usually less costly. $\endgroup$ – Klaus Draeger Mar 14 '14 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.