Language Complexity of Unimodal Systems
Petr Kůrka
Faculty of Mathematics and Physics,
Charles University in Prague,
Malostranské námestí 25,
CZ-118 00 Praha 1, Czechia
Abstract
The complexity of formal languages which are generated by 
-unimodal systems on interval covers is studied. It is shown that there exist -unimodal systems with nonrecursive languages, those with recursive but not context-sensitive languages, and those with context-sensitive but not regular languages. It is also shown that -unimodal systems with regular languages include all systems with finite, periodic, and preperiodic kneading sequences, but also all infinitely renormalizable systems. Finally, it is shown that systems with zero topological entropy might be characterized by periodic languages (a subclass of regular languages), and systems with unique fixed points can be characterized by bounded periodic languages.
