A new proof for the DOL sequence equivalence problem and its implications. (English) Zbl 0586.68066

Čulik, Karel II; Karhumäki, Juhani

The book of L, dedic. A. Lindenmayer Occas. 60th Birthday, 63-74 (1986).

[For the entire collection see Zbl 0575.00023.]
Recently, the validity of the Ehrenfeucht Conjecture on test sets for morphisms has been established. Based on this result we give an entirely new proof of the decidability of the DOL sequence equivalence problem. The new technique is more powerful and allows us to prove that the sequence equivalence problems for HDOL and DTOL sequences are decidable, as well. We also survey the known results on various generalizations of the DOL sequence equivalence problem.

MSC:

68Q45

Formal languages and automata

Keywords:

decidability

Citations:

Zbl 0575.00023