CS Paper Radar

Two-State Max-Plus Comparison Is Decidable

Keigo Oka

cs.FL cs.DS ·submitted 2026-09-01 03:56 UTC · v2

Abstract

Daviaud, Guillon, and Merlet proved that comparison of max-plus automata is undecidable under a fixed state bound of 553 and explicitly left the range from 2 to 552 states open. We resolve the two-state endpoint. More strongly, given an arbitrary finite max-plus automaton $A$ and a max-plus automaton $B$ with at most two states, it is decidable whether $[\![A]\!](w)\leq [\![B]\!](w)$ for every word $w$. The structural reason is a one-dimensional projective normal form for two-state dynamics. Outside an effective bounded region, a transition has one of three tail behaviors: it propagates the unbounded projective gap with gap-independent height increment, forgets the gap with gap-independent height increment, or reads the gap magnitude into the height increment and then forgets it. In particular, any transition whose output depends on the unbounded gap necessarily destroys that gap. This yields an exact one-counter realization of $B$. Effective semilinearity of context-free Parikh images then reduces comparison to Presburger arithmetic. As a consequence, two-state max-plus comparison, equivalence, and positivity are decidable.

Comment
8 pages. Revised presentation and clarified the proof; main result unchanged

Closest papers

Nearest neighbours by meaning across the whole index.

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.63
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown automaton, we first consider, for each string in its language, the minimum number of turns made in accepting computations (weak measure). We prove that it is decidable whether a pushdown automaton accepts a bounded language in a constant number of turns and whether it accepts a bounded language in k turns, for any given k>=0. This is in contrast to the general case, in which these problems are known to be undecidable, with the exception of acceptance in 0 turns, which is decidable. Furthermore, we prove that when the number of turns sufficient to accept a bounded language is not limited by any constants, it linearly grows with respect to the input length. Also this is in contrast with the general case where, for each nonnegative k, there exists a language for which the number of turns necessary and sufficient is of the order of log^(k), the k times composition of the logarithm with itself. We also prove that, when the costs of all accepting computations are taken into account (accept measure), a linear lower bound for the number of turns, if not limited by any constants, holds even removing the restriction to bounded languages.

0.43

Non-recursive trade-offs for two-way machines

cs.FL ·2026-10-08 ·Christos Kapoutsis
top venuetheoryhighly cited similarity 0.62
Abstract · International Journal of Foundations of Computer Science, 16:943-956, 2005. Number of pages: 14. Number of figures: 0

If the machines of some type A have enough resources to (i) solve problems that no machine of type B can solve, and (ii) simulate any unary two-way deterministic finite automaton that has access to a linearly-bounded counter, then typically no recursive function can upper bound the increase in the size of description when a machine of type A is replaced by an equivalent machine of type B.

0.68

A Factor-Two Lower Bound for Complementing Two-Way Deterministic Finite Automata

cs.FL cs.CC ·2026-10-10 ·Sudais Arif
theoryhot direction similarity 0.61
Abstract · 18 pages, 1 figure

For every $n\ge22$, we construct a language over a fixed three-letter alphabet whose two-way deterministic state complexity is $n$ and whose complement has state complexity $2n$. Acceptance is at the left endmarker, and infinite computations reject. The lower bound holds for arbitrary deterministic recognizers. The proof uses the group of transformations induced by the witness to constrain the behavior of a smaller recognizer, then derives a contradiction from a permutation query problem. A matching halting complement follows from a $2n$-state construction for sources whose destination states determine the direction of each transition. Splitting states by incoming direction gives a $2n+2b$ upper bound for general sources, where $b$ counts states entered in both directions. In the acceptance-anywhere model of Geffert, Mereghetti, and Pighizzini, the same family has exact complexities $N$ and $2N-1$ for every $N\ge23$.

0.39

Exact versus unique nondeterministic automatic complexity

cs.FL math.LO ·2026-08-23 ·Bjørn Kjos-Hanssen, Travis Rivera Petit
similarity 0.61
Abstract

The exact nondeterministic automatic complexity $A_{Ne}(x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word of length $|x|$; the unique nondeterministic automatic complexity $A_N(x)$ additionally requires the accepting computation to be unique. Chen, Kjos-Hanssen, Koswara, Richter, and Stephan (FSTTCS 2025) asked whether the two measures can differ. We answer this affirmatively: the binary word $w=1101000000100$ satisfies $A_{Ne}(w)=6<7=A_N(w)$. The separation is witnessed by a six-state automaton whose sole accepted word of length $13$ is $w$, accepted along exactly three computation paths. The matching lower bounds were established by exhaustive search and by SAT solvers, with proofs of unsatisfiability certified in the DRAT format. An exhaustive census shows that $13$ is the least length of a separating word over any alphabet, binary or not, and that up to renaming of letters the separating words of length $13$ are precisely $365$ letter-mergings of the single seven-letter word $0123444445126$, all with $A_{Ne}=6<7=A_N$; exactly eight of them are binary. The separating word and the core of the verification were found by an artificial intelligence agent.

0.22

Unary Versus Binary Two-Way Automata

cs.FL ·2026-08-25 ·Viliam Geffert, Vincent Hlaváč, Rastislav Královič
publishedhot direction similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

If L is a unary language, then its binary coded version bin(L) is a binary language containing all binary strings representing any 0^x in L. It is known that if a unary language L is regular and can be recognized by a minimal one-way deterministic finite automaton (1DFA) with n states, then its binary coded version is also regular and can be recognized by a 1DFA with at most n states, but at least 1+log(n) states. Here we shall present related results for two-way automata (2DFAs). First, we shall show that each unary 2DFA A' with n states can be converted to a 2DFA A'' recognizing bin(L(A')) with at most O(n.log n) states. If A' is minimal and uses only loops of odd lengths, A'' will use at most 2n+2 states, but it must use at least n states. For each n>=7, we shall also present a unary witness language for which a minimal 2DFA uses exactly n states, but any minimal 2DFA recognizing its binary coded version uses at least n states, but less than n+log(n) states.

0.46

From k+1 to k heads the descriptive trade-off is non-recursive

cs.FL ·2026-10-08 ·Christos Kapoutsis
theoryhot directionhighly cited similarity 0.60
Abstract · Proceedings of DCFS 2004, pp. 213-224. Number of pages: 13. Number of figures: 0

We prove that no recursive function can upper bound the increase in the size of description when a two-way deterministic finite automaton with k+1 heads is replaced by an equivalent two-way deterministic finite automaton with k heads. This is true for all k, and remains true if the automata are unary and/or nondeterministic.

0.61

Undecidability of Reachability for Constraint Automata

cs.FL ·2026-10-11 ·Jakub Michaliszyn
theoryhot direction similarity 0.59
Abstract

We prove that reachability for constraint automata over finite binary words is undecidable. Eight registers suffice, with conjunctive guards using only equality, proper prefix, proper suffix, and infix incomparability, without word constants or concatenation. Finite-run nonemptiness, Buechi nonemptiness, and bounded Buechi nonemptiness are undecidable as consequences. For Boolean guards over equality, prefix, suffix, and prefix and suffix incomparability, Buechi nonemptiness is PSPACE-complete with arbitrarily many registers and word constants. The upper bound also allows positive infix atoms and yields PSPACE-completeness of prefix--suffix LTL satisfiability.

0.31

Deterministic Bandwidth of Finite Languages

cs.FL ·2026-08-25 ·Da-Jung Cho, Szilárd Zsolt Fazekas, Max Wiedenhöft
publishedtheory similarity 0.59
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Bandwidth restricts how far transitions can move under an ordering of the states in an automaton. While every finite language admits a bandwidth-2 NFA representation, the deterministic setting is substantially more restrictive. We investigate the bandwidth of partial DFAs accepting finite languages. We show that bounded bandwidth imposes strong structural restrictions on deterministic representations. We prove that there is an infinite hierarchy of classes of finite languages defined by deterministic bandwidth. As a special case of interest, we consider finite languages accepted by bandwidth-1 partial DFAs, and show that they admit a positional characterization, which yields a polynomial-time decision algorithm. We further study how the minimum DFA bandwidth can be estimated from the structure of the minimal DFA. We derive computable upper and lower bounds based on position-unfolding, and local growth of reachable residual states. These bounds can be computed efficiently and differ by at most a linear factor in the maximum word length. We also present a simple language family where the bounds match exactly.

0.48