The phenomenon of non-recursive trade-offs
The phenomenon of non-recursive trade-offs
复制标题
非递归权衡现象
DOI：
--
复制
发表时间：
2005
影响因子：
0.8
通讯作者：
Martin Kutrib
中科院分区：
文献类型：
--
作者：
Martin Kutrib
不同语言表示之间的非递归权衡揭示了一个基本现象。描述的经济性可以是任意的。本文的目的是研究相对简洁性不受递归限制的语言的不同表示的主要方面和结果。讨论了描述系统的基本性质和合理的尺寸度量，并给出了文献中出现的统一的基本证明方案。给出了结果的全面概述。最后，给出了一些新的结果。特别地，证明了在无限单向k头有限自动机层次的每两层之间存在一种非递归的权衡。此外，非递归的权衡是非确定性2头和确定性k头自动机之间显示。
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 are shown. In particular, it is proved that between each two levels of the infinite one-way k-head finite automata hierarchies there is a non-recursive trade-off. Moreover, non-recursive trade-offs are shown between nondeterministic 2-head and deterministic k-head automata.