4
$\begingroup$

Given two NFW $A$ and $B$, we regarded $A$ and $B$ as Büchi automata.

We can show that the containment property is not preserved in Büchi automata. That is, we can construct a example: $L(A) \subseteq L(B)$ when A and B are both NFW, but $L_\omega(A) \nsubseteq L_\omega(B)$ when A and B are both Büchi automata.

My question is : Are there any interesting properties is preserved in Büchi automata? Conversely, given two Büchi automata, are there any interesting properties is preserved in NFW?

$\endgroup$
4
  • $\begingroup$ en.wikipedia.org/wiki/B%C3%BCchi_automaton $\endgroup$ Feb 21, 2013 at 16:53
  • $\begingroup$ I am no expert, but I believe that being star-free is preserved. $\endgroup$ Feb 21, 2013 at 16:54
  • $\begingroup$ There is an analogue of the pumping lemma, by essentially the same proof. $\endgroup$ Feb 21, 2013 at 16:58
  • $\begingroup$ Does "NFW" mean finite nondeterministic automaton? If this is the case, NFA is a much more standard acronym. $\endgroup$
    – J.-E. Pin
    Aug 14, 2015 at 13:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.