Context-free sequences

A sequence w over a finite alphabet A is generated by a uniform automaton if there exists an automaton labelled on {0, … ,k−1} for some k > 1 and recognizing for each output a in A the set of positions of a in w expressed in base k. Automatic sequences are generated by finite automata. By considering pushdown automata instead of finite ones, we generate exactly the context-free sequences. We distinguish the subfamilies of unambiguous, deterministic, real-time deterministic contextfree sequences associated with the corresponding families of pushdown automata. We study the closure under shift, product, morphisms, inverse substitutions and various extractions of these four families of contextfree sequences. Additionally, we show that only using multiplicatively dependent bases yields the same set of context-free sequences. © Springer International Publishing Switzerland 2014.