On the Decidability of some Equivalence Problems for D0L-Systems

Authors

  • Mogens Nielsen

DOI:

https://doi.org/10.7146/dpb.v2i20.6439

Abstract

One of the questions of the longest open standing in the area of Lindenmayer-systems is the decidability of the equivalence problem for deterministic, informationless L-systems (DOL-Systems). This and some related equivalence-problems (equivalence with respect to the set and the sequence of generated words, Parikh-vectors and word-lengths) are investigated. Some of these related problems are shown to be recursively solvable, and the implications of these results on the main open problem mentioned above are discussed. (The paper has been accepted for publication in Information and Control).

Downloads

Published

1973-12-01

How to Cite

Nielsen, M. (1973). On the Decidability of some Equivalence Problems for D0L-Systems. DAIMI Report Series, 2(20). https://doi.org/10.7146/dpb.v2i20.6439