The Frobenius Problem and Its Generalizations

DOI10.1007/978-3-540-85780-8_5zbMath1161.11319OpenAlexW1488679966MaRDI QIDQ3533000

Jeffrey O. Shallit

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_5

zbMATH Keywords

sortingFrobenius numberpostage-stamp problemcoin change problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Combinatorics on words (68R15) Formal languages and automata (68Q45) Linear Diophantine equations (11D04)

Related Items

Methods for the estimation of the size of lookahead tree state-space ⋮ A two-cyclic queuing system ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Unary finite automata vs. arithmetic progressions ⋮ Expressive capacity of subregular expressions ⋮ Concatenation-free languages

Uses Software

• Frobby

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved upper bounds on Shellsort
• Finite automata and unary languages
• Lattice translates of a polytope and the Frobenius problem
• The state complexities of some basic operations on regular languages
• On the linear diophantine problem of Frobenius
• On shellsort and the Frobenius problem
• Complexity of the Frobenius problem
• Solving thousand-digit Frobenius problems using Gröbner bases
• Faster algorithms for Frobenius numbers
• Note on Linear Forms
• A new upper bound for Shellsort
• Solution to a linear diophantine equation for nonnegative integers
• A Postage Stamp Problem
• A Circle-Of-Lights Algorithm for the "Money-Changing Problem"
• The Frobenius Problem in a Free Monoid
• On a Problem of Partitions