Is there any general result to show that which automaton is more succinct? I have a set of LTL properties and I would like to know (show) which automaton is more efficient in term of state number and edge number.

  • $\begingroup$ Can you expand the main body of your question to make it independent of the title? Try to be more elaborate. $\endgroup$ – Yuval Filmus Mar 17 '17 at 11:35
  • $\begingroup$ Have you checked any small examples? $\endgroup$ – Michael Klein Mar 17 '17 at 14:05
  • $\begingroup$ @MichaelKlein Yes, Actually Buchi was way better in my examples but I just wanted to know if it is a general argument or not. $\endgroup$ – Perissiane Mar 17 '17 at 14:27
  • $\begingroup$ From a discussion with one of my friends for state numbers: "the rule of thumb is determinism costs 2EXP, nondeterminism costs EXP". So can we just recon that Rabin automaton, because it is deterministic, needs more states? $\endgroup$ – Perissiane Mar 21 '17 at 13:56
  • $\begingroup$ @MichaelKlein can you take a look at the comment above? $\endgroup$ – Perissiane Mar 22 '17 at 10:18

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.