On Measuring Non-Recursive Trade-Offs

Details On Measuring Non-Recursive Trade-Offs On Measuring Non-Recursive Trade-Offs

2009-07-29

arxiv.org/abs/0907.5063v1

EPTCS 3, 2009, pp. 141-150

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.4204/EPTCS.3.13

We investigate the phenomenon of non-recursive trade-offs between descriptional systems in an abstract fashion. We aim at categorizing non-recursive trade-offs by bounds on their growth rate, and show how to deduce such bounds in general. We also identify criteria which, in the spirit of abstract language theory, allow us to deduce non-recursive tradeoffs from effective closure properties of language families on the one hand, and differences in the decidability status of basic decision problems on the other. We develop a qualitative classification of non-recursive trade-offs in order to obtain a better understanding of this very fundamental behaviour of descriptional systems.

Affiliated with

Also associated with

No associations

Rating

On Measuring Non-Recursive Trade-Offs 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 On Measuring Non-Recursive Trade-Offs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Measuring Non-Recursive Trade-Offs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521391