TY - JOUR

T1 - The Frobenius problem for homomorphic embeddings of languages into the integers

AU - Dekking, Michel

PY - 2018

Y1 - 2018

N2 -
Let S be a map from a language Lto the integers satisfying S(vw) =S(v) +S(w)for all v, w ∈L. The classical Frobenius problem asks whether the complement of S(L)in the natural numbers will be infinite or finite, and in the latter case the value of the largest element in this complement. This is also known as the ‘coin-problem’, and Lis the full language consisting of all words over a finite alphabet. We solve the Frobenius problem for the golden mean language, any Sturmian language and the Thue–Morse language. We also consider two-dimensional embeddings.

AB -
Let S be a map from a language Lto the integers satisfying S(vw) =S(v) +S(w)for all v, w ∈L. The classical Frobenius problem asks whether the complement of S(L)in the natural numbers will be infinite or finite, and in the latter case the value of the largest element in this complement. This is also known as the ‘coin-problem’, and Lis the full language consisting of all words over a finite alphabet. We solve the Frobenius problem for the golden mean language, any Sturmian language and the Thue–Morse language. We also consider two-dimensional embeddings.

KW - Frobenius problem

KW - Golden mean language

KW - Paperfolding morphism

KW - Sturmian language

KW - Thue–Morse language

UR - http://www.scopus.com/inward/record.url?scp=85046165273&partnerID=8YFLogxK

UR - http://resolver.tudelft.nl/uuid:28fc3854-d96e-48d3-bbd9-d4bf9530db90

U2 - 10.1016/j.tcs.2018.04.023

DO - 10.1016/j.tcs.2018.04.023

M3 - Article

AN - SCOPUS:85046165273

VL - 732

SP - 73

EP - 79

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -