Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
复制标题
一元字母表上的连接文法：不可判定性和无界增长
DOI：
10.1007/s00224-008-9139-5
复制
发表时间：
2007
影响因子：
0.5
通讯作者：
A. Okhotin
中科院分区：
文献类型：
--
作者：
Artur Jeż;A. Okhotin
最近已经证明（Jeange，DLT 2007），合取语法（即由合取增强的上下文无关语法）在单字母表上生成一些非正则语言。本文改进了这一结果，通过构建一个更大的一类一元语言的合取语法。结果意味着不可判定的一元合取文法的一些决策问题，以及不存在的递归函数的增长速度的生成语言的边界。该论点的一个重要步骤是模拟元胞自动机，使用语言方程识别数字的位置符号。
It has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some non-regular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as non-existence of a recursive function bounding the growth rate of the generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.