The Frobenius Problem and Its Generalizations

DOI10.1007/978-3-540-85780-8_5MaRDI QIDQ3533000zbMATH OpenOpenAlexFDO

Authors Jeffrey 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

coin change problemFrobenius numberpostage-stamp problemsorting

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5041220
• The Frobenius problem for classes of polynomial solvability.
• The Diophantine problem of Frobenius
• An extreme family of generalized Frobenius numbers
• An algorithm for the Frobenius problem

Cites work

• A Circle-Of-Lights Algorithm for the "Money-Changing Problem"
• A new upper bound for Shellsort
• A Postage Stamp Problem
• Complexity of the Frobenius problem
• Faster algorithms for Frobenius numbers
• Finite automata and unary languages
• Frobenius numbers by lattice point enumeration
• scientific article; zbMATH DE number 18540 (Why is no real title available?)
• scientific article; zbMATH DE number 50662 (Why is no real title available?)
• scientific article; zbMATH DE number 4115989 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• Improved upper bounds on Shellsort
• Lattice translates of a polytope and the Frobenius problem
• Note on Linear Forms
• On a Problem of Partitions
• On shellsort and the Frobenius problem
• On the linear diophantine problem of Frobenius
• Regular expressions: new results and open problems
• Solution to a linear diophantine equation for nonnegative integers
• Solving thousand-digit Frobenius problems using Gröbner bases
• The Frobenius problem in a free monoid
• The state complexities of some basic operations on regular languages

Cited in

(31)

• On the geometry of the Frobenius problem
• The Frobenius problem for classes of polynomial solvability.
• The generalized Favard problem
• The parametric Frobenius problem
• Concatenation-free languages
• Methods for the estimation of the size of lookahead tree state-space
• Distributed graph problems through an automata-theoretic lens
• The Diophantine problem of Frobenius
• scientific article; zbMATH DE number 2186972 (Why is no real title available?)
• An extreme family of generalized Frobenius numbers
• An algorithm for solving the Frobenius problem using Gröbner bases
• The Frobenius number of geometric sequences
• scientific article; zbMATH DE number 5557899 (Why is no real title available?)
• scientific article; zbMATH DE number 18540 (Why is no real title available?)
• scientific article; zbMATH DE number 166132 (Why is no real title available?)
• scientific article; zbMATH DE number 169254 (Why is no real title available?)
• scientific article; zbMATH DE number 740302 (Why is no real title available?)
• scientific article; zbMATH DE number 1870541 (Why is no real title available?)
• The Frobenius problem in a free monoid
• Frobenius templates in certain 2 2 matrix rings
• Expressive capacity of subregular expressions
• A postage problem
• Commutative algebra and the linear Diophantine problem of Frobenius
• A Frobenius problem suggested by prime \(k\)-tuplets
• Subregular expressions with two operations
• String assembling systems: origins and directions
• Complexity of unary exclusive nondeterministic finite automata
• Two graphs: resolving the periodic reversibility of one-dimensional finite cellular automata
• An optimal lower bound for the Frobenius problem
• A two-cyclic queuing system
• Unary finite automata vs. arithmetic progressions

Describes a project that uses

Uses Software

• Frobby

This page was built for publication: The Frobenius Problem and Its Generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533000)