On Measuring Non-Recursive Trade-Offs

Hermann Gruber
Markus Holzer
Martin Kutrib

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.

In Jürgen Dassow, Giovanni Pighizzini and Bianca Truthe: Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany, July 6-9, 2009, Electronic Proceedings in Theoretical Computer Science 3, pp. 141–150.
Published: 30th July 2009.

ArXived at: http://dx.doi.org/10.4204/EPTCS.3.13 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org