On Measuring Non-Recursive Trade-Offs
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 abstrac...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2009-07-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/0907.5063v1 |
| _version_ | 1811281709443842048 |
|---|---|
| author | Hermann Gruber Markus Holzer Martin Kutrib |
| author_facet | Hermann Gruber Markus Holzer Martin Kutrib |
| author_sort | Hermann Gruber |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-13T01:38:28Z |
| format | Article |
| id | doaj.art-4af4e38787464ec89f77e29fc04255b1 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-13T01:38:28Z |
| publishDate | 2009-07-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-4af4e38787464ec89f77e29fc04255b12022-12-22T03:08:17ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802009-07-013Proc. DCFS 200914115010.4204/EPTCS.3.13On Measuring Non-Recursive Trade-OffsHermann GruberMarkus HolzerMartin KutribWe 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.http://arxiv.org/pdf/0907.5063v1 |
| spellingShingle | Hermann Gruber Markus Holzer Martin Kutrib On Measuring Non-Recursive Trade-Offs Electronic Proceedings in Theoretical Computer Science |
| title | On Measuring Non-Recursive Trade-Offs |
| title_full | On Measuring Non-Recursive Trade-Offs |
| title_fullStr | On Measuring Non-Recursive Trade-Offs |
| title_full_unstemmed | On Measuring Non-Recursive Trade-Offs |
| title_short | On Measuring Non-Recursive Trade-Offs |
| title_sort | on measuring non recursive trade offs |
| url | http://arxiv.org/pdf/0907.5063v1 |
| work_keys_str_mv | AT hermanngruber onmeasuringnonrecursivetradeoffs AT markusholzer onmeasuringnonrecursivetradeoffs AT martinkutrib onmeasuringnonrecursivetradeoffs |