Konferenzpaper

Jahr der Veröffentlichung: 2005

Seiten: 957-973

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 16

Heftnummer: 5

ISSN: 0129-0541

DOI Link: https://doi.org/10.1142/S0129054105003406

Konferenz: 6th International Workshop on Descriptional Complexity of Formal Systems

Verlag: World Scientific Publishing

Abstract: 
Non-recursive trade-offs between different representations of languages reveal a basic phenomenon. The gain in economy of description can be arbitrary. The purpose of this paper is to survey the main aspects and results regarding different representations of languages whose relative succinctness is not recursively bounded. Basic properties of descriptional systems and reasonable size measures are addressed, and the unified fundamental proof schemes emerging from the literature are presented. A comprehensive overview of results is given. Finally, some new results axe shown. In particular, it is proved that between each two levels of the infinite one-way kappa-head finite automata hierarchies there is a non-recursive trade-off. Moreover, non-recursive trade-offs are shown between nondeterministic 2-head and deterministic kappa-head automata.

Harvard-Zitierstil: Kutrib, M. (2005) The phenomenon of non-recursive trade-offs, International Journal of Foundations of Computer Science, 16(5), pp. 957-973. https://doi.org/10.1142/S0129054105003406

APA-Zitierstil: Kutrib, M. (2005). The phenomenon of non-recursive trade-offs. International Journal of Foundations of Computer Science. 16(5), 957-973. https://doi.org/10.1142/S0129054105003406