Deciding context equivalence of binary overlap-free words in linear time |
| |
Authors: | Arseny M Shur |
| |
Institution: | 1. Institute of Mathematics and Computer Science, Ural Federal University, 620000, Ekaterinburg, Russia
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|