Article ID Journal Published Year Pages File Type
9657803 Theoretical Computer Science 2005 16 Pages PDF
Abstract
This paper proves the decidability of several problems in the theory of HD0L, D0L and PD0L systems, some of which that have been proved before but are now proved in a different way. First, the paper tackles the decidability of the nilpotency of HD0L systems and the infinitude of PD0L languages. Then, we prove the decidability of the problem of momentary stagnation of the growth function of PD0L systems. Finally, we suggest a way to solve the decidability of the momentary stagnation of the growth function of D0L systems, proving the decidability of the infinitude of HD0L as a trivial consequence.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,