On the Decidability of some Equivalence Problems for D0L-Systems | Zendy

Mogens Nielsen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Decidability of some Equivalence Problems for D0L-Systems

Author(s) -

Mogens Nielsen

Publication year - 1973

Publication title -

daimi report series

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).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research