3

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?

flag
en.wikipedia.org/wiki/B%C3%BCchi_automaton – Benjamin Steinberg Feb 21 at 16:53
I am no expert, but I believe that being star-free is preserved. – Benjamin Steinberg Feb 21 at 16:54
There is an analogue of the pumping lemma, by essentially the same proof. – Joel David Hamkins Feb 21 at 16:58

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.