General Idempotency Languages Over Small Alphabets
Abstract
Idempotency languages are generated from a single word by iterated application of rules of the form um→un for natural numbers m and n. We investigate these languages over alphabets of only one or two letters. The conditions under which the underlying rewrite relations are confluent are fully characterized. Then for many combinations of the parameters m and n we answer the question, whether the corresponding idempotency languages are regular or not. What remains open are only the cases where 2≤m<n.
Communicated by Kayoko Shikishima-Tsuji