Culik, Karel II; Karhumäki, Juhani The decidability of the DT0L sequence equivalence problem and related decision problems. (English) Zbl 0641.68117 The very knowledge of coding, Stud. Hon. Aimo Tietäväinen Occas. 50th Birthday, 43-54 (1987). Summary: [For the entire collection see Zbl 0621.00032.] We show that it is decidable whether or not two given morphisms agree word by word on a given DT0L language. Hence, a nontrivial generalization of the famous D0L sequence equivalence problem, namely the DT0L sequence equivalence problem is decidable. We also show that our main decidability result holds for some larger families of (morphically defined) languages. MSC: 68Q45 Formal languages and automata 68Q42 Grammars and rewriting systems Keywords:equivalence problem; decidability Citations:Zbl 0621.00032 PDFBibTeX XML