2011/05/26 by Alan Guo, Ezra Miller, Guo, Alan +1
Computer Science · Mathematics · #05A15 (Primary) #05E40 #11P21 #20M14 #52B20 (Secondary) #68Q25 #68W30 #91A05 #91A46 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Commutative Algebra (math.AC) #Computability, Logic, AI Algorithms #FOS: Mathematics #math.AC #math.CO #msc:05A15 #msc:05E40 #msc:11P21 #msc:20M14 #msc:52B20 #msc:68Q25 #msc:68W30 #msc:91A05 #msc:91A46 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1105.5413
12 pages, no figures
arxiv created 2011/05/26 · openalex publication_date 2011/05/26 · arxiv updated 2011/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper provides effective methods for the polyhedral formulation of impartial finite combinatorial games as lattice games. Given a rational strategy for a lattice game, a polynomial time algorithm is presented to decide (i) whether a given position is a winning position, and to find a move to a winning position, if not; and (ii) to decide whether two given positions are congruent, in the sense of misère quotient theory. The methods are based on the theory of short rational generating functions.