Queues, Stacks, and Transcendentality at the Transition to Chaos

Cristopher Moore and Porus Lakdawala

98-12-112

We examine the one-humped map at the period-doubling transition to chaos, and ask whether its long-term memory is stacklike (last-in, first-out) or queuelike (first-in, first-out). We show that it can be recognized by a real-time automaton with one queue, or two stacks, and give several new grammatical characterizations of it. We argue that its memory has a queue-like character, since a single stack does not suffice. We also show that its dynamical zeta function, generating function, and growth function are transcendental. The same results hold for any period-multiplying cascade. We suggest that transcendentality might be a sign of dynamical phase transitions in other systems as well.