Periodic D0L languages (Q1093376)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Periodic D0L languages |
scientific article |
Statements
Periodic D0L languages (English)
0 references
1986
0 references
The following problem in combinatorial semigroup theory and in formal language theory is proved to be decidable. Given a morphism \(h:A^*\to A^*\) and a word \(w\in A^*\) over the alphabet A, is the sequence w, h(w), \(h^ 2(w)\),... eventually periodic, that is, does there exist integers i, p and \(e>0\) such that \(h^{i+p}(w)=(h^ i(w))^ e\)?
0 references
free semigroups
0 references
D0L-systems
0 references
periodicity of words
0 references
formal language
0 references
