Descriptional Complexity - An Introductory Survey
Descriptional Complexity - An Introductory Survey
复制标题
描述复杂性 - 介绍性调查
DOI：
10.1142/9781848165458_0001
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Martin Kutrib
中科院分区：
文献类型：
--
作者：
M. Holzer;Martin Kutrib
本文的目的是从更抽象的角度介绍关于语言的不同表示的相对简洁性的主要方面和结果，例如有限自动机、正则表达式、下推自动机及其变体、上下文无关文法和描述系统。讨论了这些描述系统的基本性质及其大小度量。不同表示之间的权衡要么是由某个递归函数限定的，要么是揭示了描述的经济收益可以是任意的现象。在后一种情况下，没有作为上界的递归函数。我们讨论了与形式系统的描述复杂性相关的发展。提出的结果没有得到证实，但我们只是提请注意大局和涉及的一些主要想法。
The purpose of the paper is to give an introductory survey of the main aspects and results regarding the relative succinctness of different representations of languages, such as finite automata, regular expressions, push-down automata and variants thereof, context-free grammars, and descriptional systems from a more abstract perspective. Basic properties of these descriptional systems and their size measures are addressed. The trade-offs between different representations are either bounded by some recursive function, or reveal the phenomenon that the gain in economy of description can be arbitrary. In the latter case there is no recursive function serving as upper bound. We discuss developments relevant to the descriptional complexity of formal systems. The results presented are not proved but we merely draw attention to the big picture and some of the main ideas involved.