The Frobenius problem for homomorphic embeddings of languages into the integers

Journal article (2018)

Authors

F.M. Dekking Applied Probability - EEMCS
Research Group
Applied Probability (EEMCS) (TU Delft)
Copyright: © 2018 F.M. Dekking
DOI
help_outline
https://doi.org/10.1016/j.tcs.2018.04.023
Frobenius problem Golden mean language Paperfolding morphism Sturmian language Thue–Morse language
More Info
expand_more

Published Date

2018

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Applied Probability

Abstract


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.