We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets. We show that, for each integer n ≥1, there is a D&omega n;(Σ1) -complete tree language Ln accepted by a (non deterministic) Muller tree automaton. On the other hand, we prove that a tree language accepted by an unambiguous Büchi tree automaton must be Borel. Then we consider the game tree languages W(l,k), for Mostowski-Rabin indices (, k). We prove that the D&omega n;(Σ1) -complete tree languages Ln are Wadge reducible to the game tree languageW(l,k) for k-l≥2. In particular these languagesW(l,k) are not in any class D&omega n;(Σ1) for α<ωω
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We show that it is decidable for any extended ground term rewrite system R whether there is a ground term rewrite system S such that the congrunce ↔* R generated by R is equal to the congruence↔* S generated by S. If the answer is yes, then we can effectively construct such a ground term rewrite system S. We characterize congruences generated by extended ground term rewrite systems.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.