CS Paper Radar

A Structural Framework for Succession: Continuation, Recognition, and Realization

Ilya A. Shkrob

cs.AI ·submitted 2026-11-16 02:37 UTC · v1

Abstract

Succession asks whether an entity encountered later is the same entity that entered an arrangement earlier. For an artificial system that is fine-tuned, distilled, or copied, it has to be answered. We look for a mathematical structure weak enough to cover any such case and strong enough to support general theorems, so that results follow from the structure's conditions rather than from a particular pipeline or criterion. Succession is modeled on state/modification graphs with relational lifts that compose along paths. Within this framework we separate four questions that are often conflated: which continuations a representation admits, which descendants are compatible with a modification, which are recognized as continuing the identity, and which are realized. The framework allows one to address systematically questions of symmetry, computational complexity, recoverability, and robustness to partial realization, and we establish what the structure settles in each case before any particular criterion of identity is chosen.

Comment
45 pages with tables and diagrams

Closest papers

Nearest neighbours by meaning across the whole index.

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.61
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.49

Decreasing Diagrams are Complete for Confluence

cs.LO ·2026-10-05 ·Jörg Endrullis, Ievgen Ivanov, Femke van Raamsdonk
theory similarity 0.59
Abstract

Confluence is a fundamental property of nondeterministic computations, arising from parallelism, concurrency, or freedom in the evaluation order. It guarantees that such a computation always yields the same result, regardless of the order in which steps are taken. The decreasing diagrams technique of van Oostrom is one of the most versatile methods for establishing confluence of transition systems (abstract rewriting systems). It reduces global confluence to local confluence: a system is confluent whenever its transitions admit a locally decreasing labeling. Essentially all classical confluence criteria arise as corollaries. A central question, posed by van Oostrom in 1993, asks whether the decreasing diagrams technique is complete: Does every confluent transition system admit a locally decreasing labeling? This is Problem 56 of the RTA List of Open Problems. A positive answer was known only for countable systems, and recently up to the first uncountable cardinal $\aleph_1$. The general case remained open. We settle this thirty-three-year-old problem in full. We prove that every confluent transition system admits a locally decreasing labeling using only three labels. This bound is optimal, as two labels do not suffice even at the first uncountable cardinality. It follows that this single criterion can, in principle, certify the confluence of every confluent system, and hence of every confluent program. The entire development is machine-checked in the Isabelle/HOL and Lean proof assistants and relies only on classical logic and the axiom of choice.

0.23

Complexity of Deciding Existence of Maltsev Polymorphisms of Finite Relational Structures

cs.CC cs.LO ·2026-11-10 ·Dejan Delic, Ali Syed
similarity 0.59
Abstract

In this article, we show that the problem of deciding whether a finite relational structure $\mathbf{A}$ admits a Maltsev polymorphism is a computational problem, which can be solved in polynomial time. We provide a proof of this result by reducing the problem to deciding whether a binary relational structure, associated with $\mathbf{A}$ admits such a polymorphism. In our construction of such an algorithm, we make an extensive use of a property of binary relations, which is implied by the existence of a Maltsev polymorphism, the so-called rectangularity property.

0.21

A new method for proving confluence on abstract reduction systems --- Confluence of non-E-overlapping weakly-shallow TRSs ---

cs.LO ·2026-10-07 ·Masahiko Sakai, Mizuhito Ogawa, Michio Oyamaguchi
similarity 0.59
Abstract · 68 pages, 17 figures

This paper proposes a new method for proving the confluence of an abstract reduction system (ARS) by clarifying the sufficient conditions, called compatibility and edge commutativity, for expanding a given finite sub-ARS into a confluent one by adding rewrite edges. This method can be regarded as an extension of our earlier work, which showed that a weakly non-overlapping, shallow, and non-collapsing term rewriting system (TRS) is confluent. Furthermore, we apply our method to demonstrate that a non-$E$-overlapping and weakly shallow TRS is confluent. Here, a term is weakly shallow if each defined function symbol occurs either at the root or in the ground subterms, and a TRS is weakly shallow if both sides of all its rewrite rules are weakly shallow. This drops the non-collapsing condition assumed in our previous work on weakly shallow TRSs. Moreover, since a weakly shallow TRS is non-$E$-overlapping whenever it is non-$ω$-overlapping, and the latter property is decidable, we also obtain a decidable sufficient condition for confluence: non-$ω$-overlapping and weakly shallow TRSs are confluent.

0.34

Beyond Proof of Possession: A Relational Theory of Authority

cs.CR cs.DC ·2026-11-04 ·Nicola Gallo
publishedtheory similarity 0.57
Abstract · 30 pages

Proof-of-Possession (PoP) establishes that an executor controls an artifact (key, token, credential, or capability), but such control alone determines neither the executor's relational profile nor the causal history of an execution occurrence. We separate PoP from Proof of Relationship (PoR), the semantic property that one execution occurrence validly continues another, and from authorization, which is occurrence-sensitive. The foundational change is in the semantic domain of authorization: from holders and authority-bearing artifacts to execution occurrences situated in causal histories. We give authorization models an observation-based occurrence verdict and a separate transition-admissibility relation; kernel inclusion yields a partial order on observation-kernel classes. Building on Provenance Identity Continuity (PIC) and Proof-of-Continuity (PoC), we classify executors by authorization-relevant equivalence relations whose quotients form relational profile spaces, with positive predicates over profile transitions forming a distributive lattice. This adds relational attenuation to authority attenuation: along a valid causal history, $C_{i+1}\subseteq C_i$ and $ρ_{i+1}\Rightarrowρ_i$. We prove dual monotonicity, combined closure, and origin relational closure. Two occurrences of the same authenticated executor, with the same profile and possession evidence, need not be authorization-equivalent, and within a valid PIC lineage a deputy's independent authority cannot be imported outside the origin context. Finally, we prove that the executor-dependent decision factors through the relational profile and is invariant under sound mechanisms establishing it: successor-side PoP is a possible evidence mechanism, not a necessary premise of authorization. Under explicit Witness Assumptions, a boundary-witnessed checkpoint construction realizes the premises without successor-side PoP.

0.69

Full Provenance on the COSS Causal Axis: An Event-Level Closure of Causal Attribution and Confused-Deputy Exclusion

cs.CR cs.DC ·2026-11-04 ·Nicola Gallo
publishedtheory similarity 0.57
Abstract · 19 pages

Provenance Identity Continuity (PIC) represents an authority-use event as an operation/resource behavior situated in a causal lineage, $(o,r,\ell)\in O\times R\times L$. We make the causal occurrence itself primitive: a represented security-relevant causal graph $(E,\to_c)$ in which each occurrence has a unique causal history, so the consistent event-lineage space is canonically isomorphic to $E$. The modeled execution has one causal partial order; distinct lineages are distinct causal histories inside it and may share a root while diverging into incomparable branches. PIC's $O\times R\times L$ is the authority-behavior projection of this space, and Causally Ordered Security-State (COSS) continuity generalizes it to an arbitrary behavior product over the same causal execution. On this semantics we prove an architecture-independent confused-deputy exclusion theorem. PIC continuation requires $C(e')\subseteq C(e)$ on every ordinary causal edge, so descendants are bounded by their ancestors; at an ordinary join, authority available on only one incoming branch cannot be resurrected, even when branches share a common root. Non-conservative combination must be an explicit authorized composition or relaxation event. With protected-effect mediation, an effect caused by request $q$ through an ordinary authority segment can exercise only authority in $C(q)$, so a confused-deputy state is contradictory. The result holds for any system whose protected request-to-effect causes are faithfully represented and whose ordinary authority transport satisfies PIC. We revisit Rajani, Garg, and Rezk: their value, control-flow, and initial-heap attacks are different witnesses of causal ancestry, so full provenance is an evidence mechanism for recovering edges of the causal graph, not the foundation of the PIC theorem. Finally we lift it to the COSS product of heterogeneous security-state coordinates.

0.44

From Border-Agnosticism to Causal Rewrite Systems

cs.DM cs.DC ·2026-10-16 ·Pablo Arrighi, Marin Costes, Luidnel Maignan
similarity 0.56
Abstract

Causal Graph Rewriting was recently introduced as an evolution of Causal Graph Dynamics to allow for a controlled form of asynchronism in these dynamical systems with dynamical graphs. In this context, the notion of borders---akin to dangling edges---has gained increasing importance. In this paper, we re-examine these borders, interpreting them as missing information. This perspective adds structural rigor to the framework, allowing border-agnostic causal graph rewriting to be reformulated as a rewriting system rather than a dynamical system. This shift represents a crucial step toward facilitating the treatment of reversibility.

0.10

Extending Higher-Order Critical Pairs

cs.LO ·2026-10-28 ·Johannes Niederhauser, Aart Middeldorp
similarity 0.56
Abstract

Confluence is a fundamental property of computation which implies that the nondeterminism of a system does not affect its outcomes. A key concept of confluence research in rewriting theory is the notion of critical pairs which captures the potential local sources of non-confluence. In this paper, we lift the definition of higher-order critical pairs to a more expressive class of higher-order rewrite systems. Thereby, we facilitate confluence analysis of rewrite systems which can express complex one-step computations as well as program transformations from functional programming.

0.19