Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657803 | Theoretical Computer Science | 2005 | 16 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Blanca Cases, Manuel Alfonseca,