×

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

Citations:

Zbl 0621.00032