Language Complexity of Unimodal Systems
by
Petr Kurka

We study the complexity of formal languages which are generated by unimodal systems on interval covers. We show that there exist unimodal systems which do not have recursive languages, those that have recursive but not context-sensitive languages, and systems which have context-sensitive but not regular languages. We show that systems with regular languages include all systems with finite, periodic or preperiodic kneading sequences, but also all infinitely renormalizable systems. Finally we show 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.

Date received: June 24, 1996

Copyright © 1996 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caai-61.