Loading...
Please wait, while we are loading the content...
Similar Documents
Complexity of unimodal maps with aperiodic kneading sequences
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wang, Yi Yang, Ling Xie, Huimin |
| Copyright Year | 1999 |
| Abstract | 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.its.caltech.edu/~matilde/AperiodicFormalLanguages.pdf |
| Alternate Webpage(s) | http://www.math.caltech.edu/~2014-15/2term/ma191b-sec4/AperiodicFormalLanguages.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Complexity Context-free language Context-sensitive grammar Context-sensitive language Formal language Map Programming Languages |
| Content Type | Text |
| Resource Type | Article |
