Weak index versus Borel rank

Details Weak index versus Borel rank Weak index versus Borel rank

2008-02-20

arxiv.org/abs/0802.2842v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Information Theory

Scientific paper

We investigate weak recognizability of deterministic languages of infinite trees. We prove that for deterministic languages the Borel hierarchy and the weak index hierarchy coincide. Furthermore, we propose a procedure computing for a deterministic automaton an equivalent minimal index weak automaton with a quadratic number of states. The algorithm works within the time of solving the emptiness problem.

Affiliated with

Also associated with

No associations

Rating

Weak index versus Borel rank does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Weak index versus Borel rank, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weak index versus Borel rank will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647807