CS Paper Radar

Solving polynomial equations over partial discrete dynamical systems

Maximilien Gadouleau, Sara Riva, Marius Rolland, Marie-Emile Voge

cs.DM ·submitted 2026-09-30 13:35 UTC · v1

Abstract

The analysis of observable phenomena (for instance, in biology or physics) allows the detection of dynamical behaviours. If the conditions are ideal and the number of observations is sufficient, we can represent these phenomena by a dynamical system, also called a functional digraph, that is to say a graph where each node has out-degree exactly one. Up to isomorphism, these dynamical systems, equipped with disjoint union as addition and direct product as multiplication, form a commutative semiring. Several previous studies on this semiring have aimed to establish algebraic properties (primality, injectivity) or complexity results (division, factorisation). However, no work has yet been conducted on graphs derived from imperfect observations that result in missing transitions or nodes, in other words, in cases where each node in the graph has an out-degree of at most one. In this case, we say that the system is partial. In this paper, we show that partial dynamical systems, up to isomorphism and equipped with the same addition and multiplication, still form a commutative semiring. We then characterise the prime elements of this semiring, which differ from those of the semiring of dynamical systems. Finally, we highlight two properties shared by both semirings. First, injective univariate polynomials admit the same characterisation in both. Second, division can be computed in polynomial time for partial dynamical systems if and only if it can be for dynamical systems.

Closest papers

Nearest neighbours by meaning across the whole index.

Graphoid Automata, Frobenius PROPs, and Semiring Evaluation

cs.FL math.CT ·2026-10-02 ·Antonios Kalampakas
theory similarity 0.63
Abstract · 29 pages

Graphoid automata evaluate graphs by composing relations between words of states. We examine the equations that make this evaluation independent of the chosen graph expression, and what changes when relations are replaced by matrices over a commutative semiring. We prove that the classical graphoid equations are equivalent to the special commutative Frobenius equations together with the required symmetry laws. The known cospan and hypergraph presentations then describe equality of structural and labelled expressions, with the bone law deleting precisely the isolated internal vertices. We use established partition representations to compare this equality with equality of evaluated matrices. For any nonempty finite state set $Q$ and commutative semiring $K$, we give a uniform criterion for two structural expressions to have the same matrix. The criterion determines which isolated-vertex counts are distinguished and when a vanishing scalar makes matrices from different boundary partitions equal. For the canonical structure, the bone law holds precisely when $|Q|\cdot1_K=1_K$. Preserving all relational compositions is a separate requirement, equivalent to additive idempotency for $|Q|\geq2$. We then examine the characteristic matrices of the known relational structures on $Q$ given by disjoint unions of Abelian groups. Their Frobenius equations hold over every commutative semiring, whereas specialness depends on the order of each group and the bone law depends on the number of groups. These conditions specify which equations remain valid when weights are assigned to a graphoid automaton.

0.27

Discrete-time polynomial systems with inputs and outputs: structure, reachability, observability, and minimal realizations

eess.SY math.OC ·2026-09-29 ·Eduardo D. Sontag
similarity 0.59
Abstract

We study the realization problem for discrete-time input/output polynomial systems. These are formalized using tools from commutative algebra and algebraic geometry as systems whose state spaces are algebraic varieties, or more abstractly the set of k-points of an affine k-scheme, where k is an arbitrary infinite field. The input/output behaviors of such systems are described by "polynomial response maps" in which outputs are polynomial functions of past inputs. The main results show that every polynomial response map admits a canonical (quasi-reachable and algebraically observable) realization, which is unique up to isomorphism. The key to the approach is to linearize dynamics by considering a "dual" system in which states are functions defined on states. Finite dimensionality of the canonical realization, and its polynomiality, are characterized in terms of the space, algebra, and field of observables of the map, as well as in terms of algebraic input/output difference equations, and by a Jacobian rank criterion. A particular subclass consists of the maps that we call "bounded," defined by the property that their degree in the past inputs is uniformly bounded. Bounded maps are shown to be finitely realizable if and only if they are realizable by finite-dimensional state-affine systems, whose theory in turn reduces to that of rational formal power series. We also study the lattice of quasi-reachable realizations of a given map, including normal realizations. This work is an update of the PhD thesis written by the author in 1976; connections to recent work are briefly discussed in the last section.

0.38

Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics

cs.DM cs.CCmath.CO ·2026-10-12 ·Florian Bridoux, Maximilien Gadouleau, David C. Kutner, Adrien Richard
similarity 0.58
Abstract · 35 pages, 5 figures

The central object in this work is the Boolean network, a function $f:\{0,1\}^V \to \{0,1\}^V$. Often identified with $f$ is its dynamics $D_f$, the digraph with exactly $\{x \to y : f(x)=y\}$ as its arcs. The interaction graph of $f$ is the digraph $G$ on $V$ which can be thought of as representing the dependencies of the components of $f$ on one another. On the other hand, model-checking is a major field of study in graph algorithms and complexity. We consider problems at the intersection of these paradigms: for a given property $φ$, we say that a digraph $G$ is $φ$-dynamic if $G$ is the interaction graph of some Boolean network $f$ such that $D_f \models φ$. The corresponding decision problem $φ$-DYNAMIC asks whether $G$ is $φ$-dynamic. Problems of this form are well-studied in the Boolean networks community. For example, it is a well-known result that, letting $φ$ be 'No fixed points' (i.e. $\nexists x:x\to x$), $φ$-DYNAMIC is equivalent to the structural digraph problem NON-ACYCLIC, which is solvable in linear time. We establish, for the first time, properties $φ$ for which $φ$-DYNAMIC is computationally hard. These include the 'Unique fixed point' property $\exists!x:x\to x$, and a range of properties concerning the periodic points of $f$ (i.e. vertices of $D_f$ which lie on a cycle). More widely, we exhibit an infinite family of natural properties $φ$ such that $φ$-DYNAMIC is $\mathrm{NEXPTIME}$-complete, which we call PERIOD PIECE. As a special case, these include all properties of the form 'Unique cycle of length $k$' and 'Exactly $k$ fixed points' for any $k \ge 1$. On the other hand, we show that if the input digraph has bounded in-degree, then for those same problems $φ$-DYNAMIC collapses down to $\mathrm{NP}^{\mathrm{NP}}$, the second level of the polynomial hierarchy, though it remains $\mathrm{NP}^{\mathrm{NP}}$-complete.

0.26

Asymptotic completions of preordered semirings

cs.IT math.RAmath.CO ·2026-09-25 ·Péter Vrana
similarity 0.57
Abstract · 58 pages

The study of preordered semirings is motivated by applications in computer science, graph theory, and information theory, and provides tools for understanding the asymptotic preorder, which compares large powers of a pair of elements. This paper studies sequences which behave approximately as sequences of powers, but are not necessarily equivalent to geometric sequences. Our main result is that preordered semirings admit completions where such sequences, that we call approximately geometric, become equivalent to geometric sequences, and that existing characterizations of the asymptotic preorder extend to the completion. We provide several classes of examples of approximately geometric sequences in the semiring of tensors, and in the semiring of graphs. As a concrete application, we determine the strong converse exponent for binary hypothesis testing with composite Markov hypotheses.

0.34

Automatic constraints with few subpowers and graphoid recognition

cs.LO cs.FL ·2026-09-07 ·Antonios Kalampakas
theory similarity 0.57
Abstract · 23 pages, 2 figures. Reproducibility package: https://doi.org/10.5281/zenodo.22648283

Finite automata can describe relations of unbounded arity that are exponentially larger than their descriptions. We prove that constraint satisfaction for such relations is solvable in polynomial time whenever their length slices are preserved by a common fixed edge operation on a finite domain. The algorithm computes compact representations of the complete solution relation and its projections. Its main ingredient is a polynomial-time compilation of nondeterministic finite automata into the fork witnesses and small projections required by the few-subpowers algorithm. In the Mal'tsev case, a direct proof is polynomial also when the domain and operation table are supplied as input, answering the Mal'tsev tractability question for automatic constraint satisfaction. We also characterize all invariant relations of a family of 3-edge algebras with neither Mal'tsev nor near-unanimity terms. Their normal forms combine Boolean activity constraints with affine value spaces and yield canonical quadratic-bit representations constructible from NFAs or arbitrary generators. For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations. The quadratic boundary bounds are optimal in the worst case. A fixed three-state example separates polynomial-time recognition from hard exact counting.

0.42

On the Representational Geometry of Dynamic Programs

cs.LG cs.DMmath.AGmath.CO ·2026-08-25 ·Richard F. M. Lim, Ruriko Yoshida
theory similarity 0.57
Abstract · 13 pages, 7 figures; submitted to NeurIPS 2026 Workshop on Symmetry and Geometry in Neural Representations (Extended Abstract Track)

Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels --- formal polynomials and their computed functions --- connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.

0.26

Optimal Convergence of Iterative Methods for Datalogo

cs.DS ·2026-10-02 ·Simon Frisk, Sungjin Im, Paraschos Koutris, Benjamin Moseley, Hung Ngo +2 more
theory similarity 0.56
Abstract

$\mathsf{Datalog}^\circ$ has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization techniques such as semi-naïve evaluation and demand transformation. $\mathsf{Datalog}^\circ$ accomplishes this by generalizing the {\em or} and {\em and} operators of Datalog to addition and multiplication over a semiring. Finding a (minimal) fixpoint of a $\mathsf{Datalog}^\circ$ program is equivalent to finding a solution to a system of polynomial equations over the underlying semiring. Solving these systems of polynomial equations is not only a fundamental problem in the theory of $\mathsf{Datalog}^\circ$, but also has many applications in computer science, such as in databases, program analysis, and optimization. This paper resolves a key open problem in the theory of $\mathsf{Datalog}^\circ$: we prove a tight upper bound on the number of steps until convergence of iterative methods for solving these polynomial equation systems over a commutative $p$-stable semiring. In particular, we show that the number of steps until convergence is $O((p+1)n)$ where $n$ is the output size of the $\mathsf{Datalog}^\circ$ program. As the number of steps until convergence is only a proxy for the runtime of $\mathsf{Datalog}^\circ$ evaluation, we also consider the number of semiring operations used and show that, for a natural class of algorithms, $O((p+1)mn)$ is a tight upper bound, where $m$ is the maximum number of semiring operations per iteration.

0.29

Shortest Synchronizing Words on Product Automata

cs.FL ·2026-11-06 ·Henning Fernau, Igor Rystsov
similarity 0.56
Abstract

We consider some operations on finite automata graphs, in particular various product, union and merge operations, and investigate how they relate to the parameter~$\mathrm{rt}$, the \emph{length of a shortest synchronizing word}. We derive some lower and upper bounds for the operations that we study. We also examine several classes of automata (for instance, partially ordered, commutative or idempotent automata) that are preserved under these operations and show in which way the parameter $\mathrm{rt}$ behaves in these automata classes. Also, we consider automata classes that can be constructed by combining automata from better known classes; in particular, these new classes of automata will also satisfy the bound of the famous Černý conjecture. This also motivates us to study even more closure properties. In particular, we show that certain automata classes related to synchronization form pseudo-varieties. We also commence a similar study concerning the length of shortest homing sequences of Mealy automata.

0.13