Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
I am no expert, but I believe that being star-free is preserved. –  Benjamin Steinberg Feb 21 '13 at 16:54
There is an analogue of the pumping lemma, by essentially the same proof. –  Joel David Hamkins Feb 21 '13 at 16:58
Does "NFW" mean finite nondeterministic automaton? If this is the case, NFA is a much more standard acronym. –  J.-E. Pin Aug 14 at 13:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.