Deciding context equivalence of binary overlap-free words in linear time / Shur Arseny M. // SEMIGROUP FORUM. - 2012. - V. 84, l. 3. - P. 447-471.

ISSN/EISSN:

0037-1912 / нет данных

Type:

Article

Abstract:

We study the structure of the language of binary overlap-free words, which is one of the classical objects in combinatorics of words and formal languages. In a natural way, this study requires a solution to the word problem for the syntactic monoid of the language. In this paper we present an algorithm that efficiently solves this word problem. Namely, the time complexity of the algorithm is linear in the total length of compared words.

Author keywords:

Overlap-free words; Syntactic monoid; Word problem; Context equivalence SEQUENCES

DOI:

10.1007/s00233-012-9382-6

Web of Science ID:

ISI:000306590200003

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	JUN
Publisher	SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013 USA
Language	English
Keywords-Plus	SEQUENCES
Research-Areas	Mathematics
Web-of-Science-Categories	Mathematics
Author-Email	Arseny.Shur@usu.ru
Funding-Acknowledgement	Russian Foundation for Basic Research {[}10-01-00793]
Funding-Text	The author acknowledges support from the Russian Foundation for Basic Research, grant 10-01-00793.
Number-of-Cited-References	15
Usage-Count-Since-2013	1
Journal-ISO	Semigr. Forum
Doc-Delivery-Number	976MY