Complexity of unimodal maps with aperiodic kneading sequences
Yi Wang, Ling Yang, Huimin Xie · Nonlinearity · 1999
It is well established that a formal language generated from a unimodal map is regular if and only if the map's kneading sequence is either periodic or eventually periodic. A previously proposed conjecture said that if a language generated from a unimodal map is context-free, then it must be regular, i.e. there exists no proper context-free language which can be generated from a unimodal map. This paper is a step forward in answering this conjecture showing that under two situations the conjecture is true. The main results of this paper are: (1) if the kneading map of a unimodal map is unbounded, then the map's language is not context-free, (2) all nonregular languages generated from the Fibonacci substitutions are context-sensitive, but not context-free. These results strongly suggest that the conjecture may be indeed true.