RAIRO - Theoretical Informatics and Applications

Table of Contents - April 2009 - Volume 43, Issue 02  

Research Article

The theorem of Fine and Wilf for relational periods

Halava, Vesaa1, Harju, Teroa1 and Kärki, Tomia1

a1 Department of Mathematics and Turku Centre for Computer Science, University of Turku, FIN-20014 Turku, Finland; vehalava@utu.fi; harju@utu.fi; topeka@utu.fi

Abstract

We consider relational periods, where the relation is a compatibility relation on words induced by a relation on letters. We prove a variant of the theorem of Fine and Wilf for a (pure) period and a relational period.

(Received April 18 2007)

(Accepted April 29 2008)

(Online publication June 5 2008)

Key Words:

  • Period;
  • partial word;
  • compatibility;
  • Fine;
  • Wilf.

Mathematics Subject Classification:

  • 68R15