6533b7dcfe1ef96bd1272882

RESEARCH PRODUCT

If a DOL language is k-power free then it is circular

Patrice SééboldFilippo Mignosi

subject

Discrete mathematicsPigeonhole principleFractional powerMathematicsInteger (computer science)Power (physics)Decidability

description

We prove that if a DOL language is k-power free then it is circular. By using this result we are able to give an algorithm which decides whether, fixed an integer k≥1, a DOL language is k-power free; we are also able to give a new simpler proof of a result, previously obtained by Ehrenfeucht and Rozenberg, that states that it is decidable whether a DOL language is k-power free for some integer k≥1.

yearjournalcountryeditionlanguage
1993-01-01
https://doi.org/10.1007/3-540-56939-1_98