The equality problem for purely substitutive words. (English) Zbl 1216.68209
Berthé, Valérie (ed.) et al., Combinatorics, automata, and number theory. Cambridge: Cambridge University Press (ISBN 978-0-521-51597-9/hbk). Encyclopedia of Mathematics and its Applications 135, 505-529 (2010).
Summary: The aim of this chapter is to prove the decidability of the equality problem for purely substitutive words. This problem, also known as the D0L
-equivalence problem, was first solved by K. Culik II
and T. Jarju
[J. Assoc. Comput. Mach. 31, 282–298 (1984; Zbl 0632.68078
)]. Our presentation follows the simpler approach given by the author in a previous paper.
|68Q45||Formal languages and automata|
|03B25||Decidability of theories; sets of sentences|
|68-01||Textbooks (computer science)|