The Frobenius problem for homomorphic embeddings of languages into the integers

Dekking, F.M.

doi:10.1016/j.tcs.2018.04.023

The Frobenius problem for homomorphic embeddings of languages into the integers

Journal article (2018)

Authors

F.M. Dekking Applied Probability -

Research Group

Applied Probability () (TU Delft)

DOI: https://doi.org/10.1016/j.tcs.2018.04.023

Frobenius problem Golden mean language Paperfolding morphism Sturmian language Thue–Morse language

To reference this document use:

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

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.

Files

46839369_TCS_D_17_00876R_post_... (pdf)

(pdf | 0.485 Mb)

- Embargo expired in 30-05-2020