EFSA Construction

• Some RE/FSA results carry over to REE/EFSA

  • for each REE, there is a nondeterministic EFSA

• but many results do not carry over ...

  • deterministic EFSA can be unacceptably large
    • matching based on deterministic EFSA is impractical
  • REE matching is NP-complete
    • matching based on nondeterministic EFSA is very inefficient

Our approach:

• build a quasi-deterministic EFSA
  • only source of nondeterminism: assigning different values to same state variable

Previous slide

Next slide

Back to first slide

View graphic version