CS Paper Radar

Word Subtraction Games

Yusuke Inoue, Hiroki Inazu

cs.FL ·submitted 2026-11-06 08:39 UTC · v1
unusual

Abstract

This note is a self-contained text on word subtraction games, combinatorial games in which players alternately remove a nonempty suffix belonging to a prescribed subtraction set from the current word. It collects and develops basic results on these games from the viewpoints of combinatorial game theory and formal language theory. We focus on the relationship between subtraction sets and the resulting languages of winning and losing positions. The topics include finite, regular, and context-free subtraction sets, as well as several variants and further developments.

Closest papers

Nearest neighbours by meaning across the whole index.

Sowing the Seeds of Intractability: Kalah is PSPACE-complete

cs.CC cs.GTmath.CO ·2026-11-12 ·Ethan Dickey, Ethan Mader
similarity 0.54
Abstract · 55 pages, 6 figures, 5 tables

Kalah is a classic two-player game in the mancala family of sowing games. Computers have solved several standard-size starting positions, but the complexity of the game on boards of growing size has remained open. We study the natural generalization in which the number of pits per side is part of the input and an arbitrary position is given, with the stone counts given in unary. We show that deciding whether a designated player can force a win from such a position is PSPACE-complete. The hard positions have Alice to move first and both stores initially empty. The same positions are hard under either common convention for capture opposite an empty pit, and with or without the bonus rule, which gives a player another turn when the last stone is sown into their own store. We introduce Line Kalah as an intermediate problem, a game on a line in which stones that leave the line effectively disappear and Alice must save each of her target pits before Bob captures it, and we reduce quantified Boolean formulas to it. The reduction uses a set of sequential timer piles whose last stones approach a group of targets, forcing Alice to choose between two captures in order to set the truth value of a variable, and a final capture gadget to test a clause chosen by Bob (only one is needed adversarially). Since either player may move any pile at any time, the stages are placed so that premature timer firings protect earlier potential targets. For a true formula, Alice's strategy against arbitrary opposing play either gains enough time to save the remaining targets (after Bob deviates from the intended play) or reaches the final test with a correctly encoded, protected input. Finally, the line positions are embedded in Kalah with both stores empty. A separate Bob pit holds the score adjustment, so the winner takes a strict majority of the stones.

0.24

From Ramsey-Based to Congruence-Based Constructions for Büchi Complementation

cs.FL cs.LO ·2026-09-05 ·Yih-Kuen Tsay, Moshe Y. Vardi
theory similarity 0.54
Abstract

The very first construction by J. Richard Büchi himself for complementing a Büchi automaton relies on a fundamental lemma about the division of an arbitrary infinite word into consecutive finite words, which was cleanly proven by invoking a specialized theorem of Ramsey. For that reason, constructions of similar nature have subsequently been labeled as Ramsey-based. Nevertheless, it suffices to have a weaker form of the lemma where the finite words come from a finite number of congruence classes, rather than arbitrary classes, that form a partition of the set of all finite words. The weaker lemma, with support of nicer properties from a congruence, can be proven without Ramsey's theorem. A commonly adopted improvement on such complementation constructions also requires the working of a congruence. This paper recounts the history and reviews using more contemporary terminology wherever possible the relevant concepts and results, to advocate renaming of Ramsey-based constructions as congruence-based constructions.

0.25

Rabin Games Revisited

cs.FL ·2026-10-11 ·Antonio Di Stasio, Moshe Y. Vardi
published similarity 0.53
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Rabin games have their roots in Michael Rabin's seminal work on automata over infinite trees and form a classical model for infinite-round games with ω-regular winning conditions. They play a central role in automata theory and temporal synthesis: translating an LTL specification into an equivalent deterministic Rabin automaton reduces synthesis to solving a Rabin game. In practice, however, Rabin games are typically solved indirectly, via parity games. One possible reason is that many direct algorithms have a factorial dependence on the Rabin index k, the number of Rabin pairs. In this work, we revisit Rabin's 1972 recursive algorithm. The algorithm is implicit in Rabin's proof and intertwined with finite-state determinacy. First, we "excavate" it as an explicit arena-based solver using standard reachability- and Büchi-game solving as basic building blocks, thus avoiding the exponential dependence on the alphabet in Rabin's original presentation. Second, we show that memoization removes the factorial term from the recursion-tree analysis. Finally, we introduce a variation that recurses on the Rabin index. These results provide a modern analysis of Rabin's recursive method and a basis for studying direct Rabin-game solvers for temporal synthesis.

0.37

Characterizing Necessary Losers to Explain Tournaments Solutions

cs.AI ·2026-08-24 ·Contet Clément, Umberto Grandi, Jérôme Mengin
published similarity 0.53
Abstract · This paper is the extended version of Contet, Grandi, Mengin. Characterizing Necessary Losers to Explain Tournaments Losers. In: Proceedings…

We study the problem of formally explaining why a candidate was not selected by a given tournament rule, by identifying sub-tournaments in which the candidate loses independently of how the rest of the tournament is completed. We define destructive minimal supports as any minimal sub-tournament satisfying this property, which in formal explainable artificial intelligence corresponds to abductive explanations for the question "Why does the loser lose the tournament?". For six common tournament solutions (maximin, uncovered set and its weighted variant, top cycle, Copeland, and Borda) we provide characterizations of when a candidate is either a necessary loser or a possible winner, we determine the size of the smallest destructive minimal supports, complemented by polynomial-time algorithms for their computation except for the case of Borda and Copeland rules which we conjecture to also be polynomial.

0.42

Subregular Expressions and Their Expressive Power

cs.FL ·2026-08-25 ·Martin Kutrib, Matthias Wendlandt
publishedsurvey similarity 0.53
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We provide a survey of several families of subregular expressions obtained by modifying the classical operator set consisting of union, concatenation, and Kleene star. More specifically, we consider expression systems based on sets of two or three operations chosen from union, intersection, complementation, concatenation, and Kleene star. The resulting language families range from finite languages to the full class of regular languages. We collect and organize known results on the expressive power and structural properties of these families. We compare the resulting language classes over unary and arbitrary alphabets and summarize known inclusion, equality, and incomparability results. The aim of this survey is to provide a unified view of the language families induced by restricted operator sets and to highlight open relations and possible directions for further research.

0.39

Construction of a DFA for Computing Grundy Numbers in the Successful Derivation Games on Right-Linear Grammars

cs.FL cs.GT ·2026-09-01 ·Yoshiaki Takata, Yusuke Inoue, Hiroyuki Seki
theory similarity 0.52
Abstract

Inoue et al. have introduced the successful derivation game (SDG) on context-free grammars (CFGs), which is a generalization of classic heap-based games including subtraction games and Keyles, and shown that the least upper bound of the Grundy numbers in the SDG on a given CFG G is undecidable in general even when we restrict G to be a linear CFG. This paper shows that for the SDG on a right-linear grammar (RLG), we can construct a DFA for computing the Grundy number of a given position. In other words, for the SDG on an RLG, the set of positions with a given Grundy number c is regular. As a corollary, the least upper bound of the Grundy numbers in the SDG on a given RLG is decidable. We also investigate the complexity of computing the least upper bound of the Grundy numbers in the SDG on a given RLG, and it is shown to be PSPACE-complete.

0.18

The Two-Level Poset Game is PSPACE-Complete

cs.CC cs.DMcs.GTmath.CO ·2026-10-14 ·Kengo Hashimoto
similarity 0.52
Abstract

Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

0.25

Independent Languages and Witnesses of Dependence (Non-satisfaction)

cs.FL ·2026-08-25 ·Stavros Konstantinidis
published similarity 0.51
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the independent language property defined by the language equation φ(X)=\emptyset, where the expression φ involves the language variable X, constant languages, and standard regular operations including transductions, but not complementation. This property consists of all languages L satisfying φ(L)=\emptyset. Depending on the choice of the operations in φ, the equation defines a broad class of codes, including combinations of standard variable-length codes and error-detecting codes. We show that any φ-independence is a Jürgensen independence, we define what a witness of non-satisfaction of φ(X)=\emptyset is, for a language L, and we show how to compute a witness of non-satisfaction when L is regular. We also discuss the complexity of the problem, showing that the decision version of the problem is PSPACE-complete.

0.48