VLDB 2026 Research / reviewers in the wild / expert
Urban Larsson
dblp:74/2542
· DBLP profile ↗
8ranked-venue papers
5as first author
2since 2021 · last 2024
0000-0003-3663-1720ORCID · corroborated
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 7 · 5 first-author · 2 since 2021Artificial intelligence and machine learning · 1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2024 | Subtraction games in more than one dimensionabstractThis paper concerns two-player alternating play combinatorial games (Conway 1976) in the normal-play convention, i.e. last move wins. Specifically, we study impartial vector subtraction games on tuples of nonnegative integers (Golomb 1966), with finite subtraction sets. In case of two move rulesets we find a complete solution, via a certain P -to- P principle (where P means that the previous player wins). Namely x ∈ P if and only if x + a + b ∈ P , where a and b are the two move options. Flammenkamp (1997) observed that, already in one dimension, rulesets with three moves can be hard to analyze, and still today his related conjecture remains open. Here, we solve instances of rulesets with three moves in two dimensions, and conjecture that they all have regular outcomes. Through several computer visualizations of outcomes of multi-move two-dimensional rulesets, we observe that they tend to partition the game board into periodic mosaics on very few regions/segments, which can depend on the number of moves in a ruleset. For example, we have found a five-move ruleset with an outcome segmentation into six semi-infinite slices. In this spirit, we develop a coloring automaton that generalizes the P -to- P principle. Given an initial set of colored positions, it quickly paints the P -positions in segments of the game board. Moreover, we prove that two-dimensional rulesets have row/column eventually periodic outcomes. We pose open problems on the generic hardness of two-dimensional rulesets; several regularity conjectures are provided, but we also conjecture that not all rulesets have regular outcomes. Urban Larsson, Indrajit Saha, Makoto Yokoo |
Theor. Comput. Sci. | 1 |
| 2021 | Golden games
Urban Larsson, Yakov Babichenko |
Theor. Comput. Sci. | 1 |
| 2020 | Partition games
Antoine Dailly, Éric Duchêne, Urban Larsson, Gabrielle Paris |
Discret. Appl. Math. | 3 |
| 2018 | The switch operators and push-the-button games: A sequential compound over rulesets
Éric Duchêne, Marc Heinrich, Urban Larsson, Aline Parreau |
Theor. Comput. Sci. | 3 |
| 2018 | Game comparison through play
Urban Larsson, Richard J. Nowakowski, Carlos Pereira dos Santos |
Theor. Comput. Sci. | 1 |
| 2017 | A cellular automaton for blocking queen games
Matthew Cook 0001, Urban Larsson, Turlough Neary |
Nat. Comput. | 2 |
| 2012 | The *-operator and invariant subtraction games
Urban Larsson |
Theor. Comput. Sci. | 1 |
| 2011 | Invariant and dual subtraction games resolving the Duchêne-Rigo conjecture
Urban Larsson, Peter Hegarty, Aviezri S. Fraenkel |
Theor. Comput. Sci. | 1 |