General Idempotency Languages Over Small Alphabets
Peter Leupold · International Journal of Foundations of Computer Science · 2016
Idempotency languages are generated from a single word by iterated application of rules of the form [Formula: see text] 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 [Formula: see text].