The Frobenius Problem and Its Generalizations

DOI10.1007/978-3-540-85780-8_5zbMath1161.11319MaRDI 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

sorting; Frobenius number; postage-stamp problem; coin change problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

68R15: Combinatorics on words

68Q45: Formal languages and automata

11D04: Linear Diophantine equations

Related Items

Expressive capacity of subregular expressions, A two-cyclic queuing system, Unary finite automata vs. arithmetic progressions, Concatenation-free languages, Methods for the estimation of the size of lookahead tree state-space

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