Open AccessOn the Decidability of some Equivalence Problems for D0L-Systems
Author(s) -
Mogens Nielsen
Publication year - 1973
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v2i20.6439
Subject(s) - decidability , equivalence (formal languages) , mathematics , sequence (biology) , discrete mathematics , set (abstract data type) , word problem (mathematics education) , combinatorics , computer science , arithmetic , genetics , biology , programming language
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).