Recurrent words and simultaneous growth in T0L systems
We prove decidability results for recurrent words in T0L schemes and systems, thereby setting 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 \(\Sigma\) and a given subalphabet \(\Delta\), 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 \(\Delta\) is at least n.
- A note on recurrent words
- Complexity of some problems concerningL systems
- scientific article; zbMATH DE number 3569855 (Why is no real title available?)
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Intercalation lemmas for tree transducer languages
- Life and death in Markov deterministic tabled OL systems
- The membership question for ETOL-languages is polynomially complete
This page was built for publication: Recurrent words and simultaneous growth in T0L systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1081308)
