Recurrent words and simultaneous growth in T0L systems

AbstractWe prove decidability results for recurrent words in T0L schemes and systems, thereby settling some recently posed open problems. However, the problems are shown to be Pspace-hard. These investigations are motivated by some questions from Markov DT0L systems.As the main tool for proving these results we introduce the notion of simultaneous growth, which is interesting in its own right. We prove that, for an ET0L language L over an alphabet Σ and a given subalphabet Δ, it is decidable whether for every positive integer n there is a word w in L such that in w the number of occurrences of every letter in Δ is at least n