On the decidability of some equivalence problems for DOL-systems
Mogens Nielsen · Information and Control · 1974
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.