A Quadratic Algorithm for Testing of Z-Codes

摘要

We consider a subclass of circular codes, namely Z-codes for bi-infinite words, that have numerous interesting properties appeared in many problems of combinatorics on words. Our major concern is a very basic problem, which is to test whether a language of finite words is a Z-code. As the main result of this paper, we give an efficient algorithm running in a quadratic polynomial time for testing of Z-codes when they are regular.