Conference paper

Publication year: 2005

Pages: 957-973

Journal: International Journal of Foundations of Computer Science

Volume number: 16

Issue number: 5

ISSN: 0129-0541

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

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

Publisher: 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 Citation style: 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 Citation style: 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