<p>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, ...)? </p>

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

CC BY-SA 3.0
2014-03-14T02:27:21.570Z
Twenty million? Hmm. How many symbols in your alphabet?
Chad Brewbaker
CC BY-SA 3.0
2014-03-14T02:44:07.297Z
two million, actually, but it is only an estimate, I should have a complete description of the plant I'm working on until the weekend, but it is a composition of 15 automata. The set of symbols is much smaller, probably it shall have no more than 50 symbols.
Lucas Alves
CC BY-SA 3.0
2014-03-14T03:08:48.910Z
So a two million node graph with constant 50 out edges? I would use, unsigned int  [2mil][50]. Depending on the distribution you might want to explicitly cache some states if they are used with extremely high frequency.
Chad Brewbaker
CC BY-SA 3.0
2014-03-14T03:14:00.137Z
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, http://www.cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/papers/PPP02.pdf
Chad Brewbaker
CC BY-SA 3.0
2014-03-14T03:28:57.653Z
Please check [about] and [help/on-topic] pages. I think this is more appropriate for [cs.se].
Kaveh
CC BY-SA 3.0
2014-03-14T03:41:20.433Z
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.
Artem Kaznatcheev
CC BY-SA 3.0
2014-03-14T07:03:28.297Z
The model-checking community uses [BDDs](http://en.wikipedia.org/wiki/Binary_decision_diagram) a lot to represent automata, e.g. [Symbolic model checking: $10^{20}$ states and beyond](http://dx.doi.org/10.1109/LICS.1990.113767).
Sylvain
CC BY-SA 3.0
2014-03-14T10:09:52.630Z
@Kaveh, I have seen the about page before asking and thought it was suitable to be asked here since data structures and automata theory are related in theoretical computer science topics.
Lucas Alves
CC BY-SA 3.0
2014-03-14T10:34:54.870Z
@Artem, usually, in Discrete Event Systems, the models are built as NFA, determinized into DFA and most of the operations are over the DFA representation. The main operations performed are the Parallel Composition of Automata (or synchronization), minimization, computation of the accessible part (reachability from the initial state) and coaccessible part (reachability form the final states).  I recommend the book of professor Wonham [link](http://www.control.utoronto.ca/DES/) (free) if someone is interested in Discrete Event Systems.
Lucas Alves
CC BY-SA 3.0
2014-03-14T12:39:08.440Z
Thank you @Sylvain, I will have a look at BDDs, sounds very promising.
Lucas Alves
CC BY-SA 3.0
2014-03-14T12:57:54.977Z
@Sylvain, I have found a paper about the use of BDDs in Discrete Event Systems [link](http://books.google.com.br/books?id=yOK2i7XmpUoC&pg=PA81) but seems it has some performance issues.
Lucas Alves
CC BY-SA 3.0
2014-03-14T15:04:33.870Z
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.
Klaus Draeger
CC BY-SA 3.0
2014-03-14T16:34:56.100Z
@KlausDraeger, I thought on doing the product on the fly, my advisor already does this in order to simulate a system (test if a word is recognized). I am not sure if it would be advantageous because in supervisor synthesis, I shall have to visit each state more than once and I am afraid of sacrificing performance over memory.
Lucas Alves
<ds.data-structures><automata-theory><application-of-theory>
Data structures for Finite Automata
Lucas Alves
# Data structures for Finite Automata

(Asked by: username_0 on 2014-03-14)

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

**Tags:** ds.data-structures, automata-theory, application-of-theory
> **Comments:**
> **username_1**: Twenty million? Hmm. How many symbols in your alphabet?  
> **username_0**: two million, actually, but it is only an estimate, I should have a complete description of the plant I'm working on until the weekend, but it is a composition of 15 automata. The set of symbols is much smaller, probably it shall have no more than 50 symbols.  
> **username_1**: So a two million node graph with constant 50 out edges? I would use, unsigned int  [2mil][50]. Depending on the distribution you might want to explicitly cache some states if they are used with extremely high frequency.  
> **username_1**: 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, http://www.cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/papers/PPP02.pdf  
> **username_2**: Please check [about] and [help/on-topic] pages. I think this is more appropriate for [cs.se].  
> **username_3**: 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.  
> **username_4**: The model-checking community uses [BDDs](http://en.wikipedia.org/wiki/Binary_decision_diagram) a lot to represent automata, e.g. [Symbolic model checking: $10^{20}$ states and beyond](http://dx.doi.org/10.1109/LICS.1990.113767).  
> **username_0**: @Kaveh, I have seen the about page before asking and thought it was suitable to be asked here since data structures and automata theory are related in theoretical computer science topics.  
> **username_0**: @Artem, usually, in Discrete Event Systems, the models are built as NFA, determinized into DFA and most of the operations are over the DFA representation. The main operations performed are the Parallel Composition of Automata (or synchronization), minimization, computation of the accessible part (reachability from the initial state) and coaccessible part (reachability form the final states).  I recommend the book of professor Wonham [link](http://www.control.utoronto.ca/DES/) (free) if someone is interested in Discrete Event Systems.  
> **username_0**: Thank you @Sylvain, I will have a look at BDDs, sounds very promising.  
> **username_0**: @Sylvain, I have found a paper about the use of BDDs in Discrete Event Systems [link](http://books.google.com.br/books?id=yOK2i7XmpUoC&pg=PA81) but seems it has some performance issues.  
> **username_5**: 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.  
> **username_0**: @KlausDraeger, I thought on doing the product on the fly, my advisor already does this in order to simulate a system (test if a word is recognized). I am not sure if it would be advantageous because in supervisor synthesis, I shall have to visit each state more than once and I am afraid of sacrificing performance over memory.  

---

## 0 answers

