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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.