The Star Height Hierarchy Vs. The Variable Hierarchy

Details The Star Height Hierarchy Vs. The Variable Hierarchy The Star Height Hierarchy Vs. The Variable Hierarchy

2009-04-10

arxiv.org/abs/0904.1701v1

Computer Science

Logic in Computer Science

Scientific paper

The star height hierarchy (resp. the variable hierarchy) results in classifying $\mu$-terms into classes according to the nested depth of fixed point operators (resp. to the number of bound variables). We prove, under some assumptions, that the variable hierarchy is a proper refinement of the star height hierarchy. We mean that the non collapse of the variable hierarchy implies the non collapse of the star height hierarchy. The proof relies on the combinatorial characterization of the two hierarchies.

Affiliated with

Also associated with

No associations

Rating

The Star Height Hierarchy Vs. The Variable Hierarchy 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 The Star Height Hierarchy Vs. The Variable Hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Star Height Hierarchy Vs. The Variable Hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-674071