Name
Abstract | ||
|---|---|---|
We characterize pairs of complementary nonhomogeneous Beatty sequences (A(n))(n> 0) and (B-n)(n> 0), with the restriction A(1) = 1 and B-1 >= 3, for which there exists an invariant take-away game having {(A(n), B-n), (B-n, A(n)) | n > 0} boolean OR {(0, 0)} as a set of P-positions. Using the notion of a Sturmian word arising in combinatorics on words, this characterization can be translated into a decision procedure relying only on a few algebraic tests about algebraicity or rational independence. This work partially answers to a question of Larsson, Hegarty, and Fraenkel, raised in [Theoret. Comput. Sci., 412 (2011), pp. 729- 735]. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1137/130948367 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
two-player combinatorial game,Beatty sequence,Sturmian word,invariant game,superadditivity | Discrete mathematics,Superadditivity,Combinatorics,Algebraic number,Sturmian word,Existential quantification,Beatty sequence,Invariant (mathematics),Combinatorics on words,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 3 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien Cassaigne | 1 | 282 | 40.80 |
| Éric Duchêne | 2 | 30 | 8.85 |
| Michel Rigo | 3 | 190 | 32.42 |