MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 '15 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.