CS Paper Radar

Wreath products of distributive quasi relation algebra frames and their application to representability

Wilmari Morton, Claudette Robinson

cs.LO ·submitted 2026-10-28 22:09 UTC · v1

Abstract

We adapt a construction by Comer (1983) for polygroups to define the wreath product of the dual frames of two distributive quasi relation algebras satisfying certain conditions and show that it is itself a frame. Frames play a role analogous to that of atom structures for relation algebras. After introducing the notion of a frame network, we establish a correspondence between frame networks satisfying certain conditions and representability of finite distributive quasi relation algebras. Next we describe a frame network for the wreath product of two finite representable distributive quasi relation algebras that satisfies the aforementioned conditions, as well as additional conditions, and use this to conclude that the complex algebra of the wreath product is a representable distributive quasi relation algebra. Thus, our construction provides a method for obtaining representable DqRAs from certain finite DqRAs that are already known to be representable.

Comment
36 pages, 14 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Arrow Operations in Categories of Lattice-valued Relations

cs.DM math.CT ·2026-08-17 ·Fatemeh Jowkar, Michael Winter
similarity 0.59
Abstract

Arrow allegories provide a convenient abstract framework to work with lattice-valued relations, or more precisely, relations that use the elements of a given Heyting algebra as truth values. One characteristic of arrow allegories is that all relations of the given arrow allegory use the same Heyting algebra ${\mathcal H}$. In this paper we want to extend this approach to allegories where relations between different objects may use different lattices of truth values and even further to relations that use a different lattice of truth values for every pair in the relation. Therefore, we define three concrete allegories, $\mathrm{Rel}({\mathcal H})$, $\mathrm{Rel}^u({\mathcal H})$ and ${\mathcal H}{\rm-Rel}$, where the allegory listed later is a full suballegory of the previous ones. These three allegories capture the three different situations mentioned above. In particular, ${\mathcal H}{\rm-Rel}$ is the standard example of an arrow category. We investigate these allegories and provide suitable categorical definitions for these structures.

0.23

Step Recursion: Mixed Stride Spectra, Path Factorization, and Synchronization Geometry

cs.CC cs.LO ·2026-08-27 ·Kirill Osipov
theory similarity 0.55
Abstract

Step recursion allows recursive computation to move through a canonical hierarchy in jumps, or strides. Suppose a function algebra is allowed to use several primitive stride lengths $L$. Composition immediately produces sums of these lengths, but it is not clear whether arbitrary nesting of mixed recursions can create any genuinely new canonical stride. We prove that it cannot: at every fixed canonical row $n\ge2$ and lower basis $m<n$, the canonical strides definable from $L$ are exactly the additive monoid $\langle L\rangle$ generated by $L$. The proof gives more information than membership alone. Every sufficiently high dependency path computing a canonical descent of stride $p$ carries total label weight exactly $p$, and the possible path signatures are precisely the additive factorizations of $p$ by the primitive stride labels. Thus the computation remembers both which strides are definable and how each one can be assembled. After saturation, inclusion between mixed-stride classes is exactly inclusion between their additive stride monoids, giving a concrete lattice description and finite certificates for inclusion. We then study several synchronized recursion clocks. Joint descent maps can encode arbitrary additive submonoids of $\mathbb N^r$, already giving continuum order complexity for $r=2$. Ordinary scalar observation, however, forgets correlations between the clocks and retains only the independent coordinate strides. This identifies precisely where synchronization information is preserved and where it collapses.

0.43

Robust Algebraic Theories of Triangle Graphs

cs.FL ·2026-08-11 ·Marius Bozga, Radu Iosif, Florian Zuleger
theory similarity 0.54
Abstract

Triangle graphs are graphs of tree-width at most three in which every edge belongs to a triangle. This class encompasses well-known graph families such as Apollonian networks. We also consider fan graphs, a subclass of triangle graphs closely related to the 3-connected triangle graphs. Our main result is an algebraic characterization of both classes. We introduce two graph algebras based on parallel composition and a ternary serial composition, and show that they generate exactly the triangle and fan graphs, respectively. These algebras provide a natural extension of the classical algebra of series-parallel graphs from tree-width two to tree-width three. Building on these characterizations, we investigate context-free, recognizable, and logically-definable graph languages. We show that counting monadic second-order logic (CMSO) is decidable over the context-free sets of triangle and fan graphs. Moreover, we prove that recognizable graph languages coincide with languages definable in CMSO for both algebras.

0.04

Graphoid Automata, Frobenius PROPs, and Semiring Evaluation

cs.FL math.CT ·2026-10-02 ·Antonios Kalampakas
theory similarity 0.53
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

Automatic constraints with few subpowers and graphoid recognition

cs.LO cs.FL ·2026-09-07 ·Antonios Kalampakas
theory similarity 0.52
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

Logical Relations on Display

cs.PL cs.LO ·2026-11-16 ·Steven Schaefer, Johnson He, Max S. New
top venue similarity 0.52
Abstract · 31 pages, 3 figures, to appear at POPL 2027

The metatheory of programming languages suffers from a lack of reuse. Researchers develop individual calculi and prove standard properties, but very few results are truly reused across papers. The problem is worse in proof assistants, where developments routinely duplicate code from prior work or rebuild it from scratch. Category theory provides the most promising path toward reusable programming language semantics. Universal properties capture the type connectives---products, functions, sums---together with their $β$/$η$ laws. Free categorical structures identify syntactic calculi. \emph{Displayed} categories provide a uniform language for specifying logical relations, and general theorems about fibrations allow their structure to be assembled compositionally. In this work we develop a library of formalized category theory in the Cubical Agda proof assistant directly applicable to programming language metatheory. We develop theories of universal properties and free categorical structures, apply them to define denotational semantics and logical relations for simply typed calculi, and identify encodings of the categorical constructions that make typechecking them tractable. From the same categorical components, we construct several familiar results via a logical relations construction---canonicity,parametricity,conservativity---and provide a proof of coherence for monoidal categories.

0.51

Finite-Context Semantics in Finitely Supported Structures

cs.LO cs.FLcs.PL ·2026-09-25 ·Gabriel Ciobanu
theory similarity 0.52
Abstract · 31 pages, 1 table, no figures

Semantics for systems with names and data often depends on finitely many distinguished values. The theory of finitely supported structures treats this dependence through invariance under permutations fixing a finite context. We develop this approach to semantics over arbitrary permutation groups and arbitrary infinite sets of atoms. The central difficulty is that finitely supported predicate spaces need not be complete lattices. We prove that, for predicates valued in a complete lattice with trivial atom action, every monotone finitely supported transformer nevertheless has least and greatest fixed points. These lie in the complete lattice determined by the transformer's context and coincide with the fixed points of every compatible monotone ambient extension equivariant under its stabilizer. Support-transfer bounds track dependencies through semantic constructions, while uniform finiteness yields finite convergence. For Boolean predicates, $m$ context-stabilizer orbits on the carrier suffice for convergence after at most $m$ iterations, even when the supported predicate lattice is orbit-infinite. We apply these results to automata, operational and modal semantics, abstract interpretation, and resource rewriting. Ultrahomogeneous atom structures in finite relational signatures yield finite cell representations, illustrated by an authorization monitor. The resulting account separates semantic existence, finite convergence, and effective computation.

0.31

Type-Checking for Pattern-Based Tree Transformations

cs.FL cs.CL ·2026-10-08 ·C. Aiswarya, Sahil Mhaskar, M. Praveen
similarity 0.52
Abstract · 26 pages, 9 figures, full version of a preprint accepted at FSTTCS 2026

We introduce and study pattern-based tree transformations. As an illustrating example, consider a source pattern $(x \cdot y) + (x \cdot z)$ and a target pattern $x \cdot (y + z)$ as a pair. This source pattern matches any expression $e$ of the form $(e_1 \cdot e_2) + (e_1 \cdot e_3)$ (by substituting $x$ with $e_1$, $y$ with $e_2$, and $z$ with $e_3$) and the pair transforms it into the expression $e_1 \cdot (e_2 + e_3)$ as dictated by the target pattern. Note that in this example, the set of expressions that match the source pattern is not a regular tree language. We propose a model of tree transformations given by a finite representation of a (possibly infinite) set of such (source pattern, target pattern) pairs. The expressive power of this model comes at the cost of undecidability of checking equivalence. Nevertheless, we show that the type-checking problem is decidable for our model of pattern-based tree transformations. The type-checking problem asks whether applying a given transformation to trees having a given regular property (type) preserves the property. Our decision procedure is by a reduction to the emptiness problem of alternating tree automata.

0.30