Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth |
| |
Authors: | Artur Jeż Alexander Okhotin |
| |
Affiliation: | 1. Institute of Computer Science, University of Wroc?aw, Wroc?aw, Poland 2. Department of Mathematics, University of Turku, Turku, Finland 3. Academy of Finland, Helsinki, Finland
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|