The Frobenius problem for homomorphic embeddings of languages into the integers

2017/12/09 by Michel Dekking, Dekking, Michel · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #68R15 #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #Graph theory and applications #math.CO #msc:68R15 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1712.03345

arxiv created 2017/12/09 · openalex publication_date 2017/12/09 · arxiv updated 2017/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let S be a map from a language L to the integers satisfying S(vw)=S(v)+S(w) for all words v,w from the language. 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 L is 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.

Cited by

• Shifting Zeckendorf and Chung-Graham representations

Related

• The abelian complexity of infinite words and the Frobenius problem
• On a Generalization of the Frobenius Number
• The Frobenius problem for the shuffle operation
• A New Algorithm for Computing the Frobenius Number
• The Computational Complexity of the Frobenius Problem