Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1216.68209
Honkala, Juha
The equality problem for purely substitutive words. (English)
[A] Berthé, Valérie (ed.) et al., Combinatorics, automata, and number theory. Cambridge: Cambridge University Press. Encyclopedia of Mathematics and its Applications 135, 505- 529 (2010). ISBN 978-0-521-51597-9/hbk

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 $\omega$-equivalence problem, was first solved by {\it K. Culik II} and {\it 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.

MSC 2000:: *68R15 Combinatorics on words
68Q45 Formal languages

Keywords: equality problem; purely substitutive words; D0L $\omega$-equivalence problem

Citations: Zbl 0632.68078

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]