CS Paper Radar

Finite-Context Semantics in Finitely Supported Structures

Gabriel Ciobanu

cs.LO cs.FLcs.PL ·submitted 2026-09-25 19:01 UTC · v1
theory

Abstract

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.

Comment
31 pages, 1 table, no figures

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.59
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

Finite Dependence and Invariance Hierarchies for Finitely Supported Structures

cs.LO math.CTmath.LO ·2026-09-14 ·Gabriel Ciobanu
similarity 0.59
Abstract · 44 pages, 2 tables, no figures. Unified synthesis of finite-dependence profiles, invariance hierarchies, freshness, context composition, orb…

Finite support indicates that the dependence is limited, but not how each finite context controls what can be observed. For a data symmetry G \leq Sym(A) and a finitely supported G-set X, we study the finite-dependence profile X^S = {x : Fix_G(S) fixes x}, indexed by finite contexts S \subseteq A. For relations on A^n this yields Boolean algebras B^{(n)}_{G,S} = Inv_n(Fix_G(S)), forming the invariance hierarchy. The hierarchy separates several nominal principles. Its meet law is the relation-algebra form of the Bojanczyk-Klin-Lasota least-support criterion, while level injectivity is fungibility. The independent join law governs composition across unions of contexts; it holds for locally oligomorphic automorphism groups of ultrahomogeneous structures in purely relational languages of arity at most two, but can fail for unary observations over ternary data. Freshness remains valid sort by sort, and its unrestricted some/any form characterizes full equality symmetry among closed groups. With least supports, orbit-finiteness implies finite context levels and a uniform support bound; under local oligomorphicity the converse also holds. Pointwise closure does not change the profile, and standard atomic-site presentations show that suitable ultrahomogeneous structures with the same age have equivalent action topoi, even though their material FSS universes may retain different external cardinal data. Contextual orientability gives a complementary pointed invariant whose threshold is the least support size of choice from unordered pairs. For countable omega-categorical structures with degenerate algebraic closure, the meet law is equivalent to weak elimination of imaginaries.

0.48

Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy

cs.FL math.GR ·2026-08-30 ·Takayuki Kuriyama
similarity 0.58
Abstract · 43 pages, 2 tables

Clark's syntactic concept lattice (SCL) records two-sided distributional structure, and Wurm extended it to tuples of arbitrary finite arity. We study \(\operatorname{cmp}_f(L)\), the minimum image size of a finite-monoid observation that preserves guarded tuple substitution through arity \(f\) on the principal layer. For regular languages, we characterize \(\operatorname{cmp}_f(L)\) exactly as the least cardinality of the codomain of an \(f\)-separating relational morphism from the pointed syntactic monoid. Let \(\operatorname{ch}(\mathbf V)\) denote the least arity at which these compression numbers stabilize uniformly over a pseudovariety \(\mathbf V\). Our main result is the following trichotomy of possible uniform heights: \(\operatorname{ch}(\mathbf V)\in\{1,2,\infty\}\), with \(\operatorname{ch}(\mathbf V)=\infty\) if and only if \(\operatorname{Synt}(\{ab\})\in\mathbf V\). Thus no finite uniform compression height \(3,4,\ldots\) occurs. The infinite case is sharp: inside \(\langle\operatorname{Synt}(\{ab\})\rangle\), every boundary \(d\to d+1\) admits unbounded compression gaps, and arbitrary finite strict prefixes of the arity hierarchy are realizable. On the finite side, commutative monoids and bands stabilize at arity one, while every completely regular syntactic monoid stabilizes by arity two; finite group kernels show that the binary bound is sharp. At unary arity, every nonempty finite simple graph is realized by an explicit length-three language, yielding an exact chromatic-number formula and NP-completeness of deciding \(\operatorname{cmp}_1(L)\le 3\) for explicitly listed length-three languages. The structural boundary between compression heights one and two remains open.

0.31

Foundations of Algebraic Architecture Theory: A Rising Sea of Geometry, Transport, Comparison, and Reconstruction

cs.SE cs.PL ·2026-09-23 ·Hiroyuki Nakahata
theory similarity 0.56
Abstract · 285 pages, 4 figures. Also archived on Zenodo with the same source: https://doi.org/10.5281/zenodo.22913488

AI-generated software changes make it increasingly important to determine what a change preserves, where local consistency fails to extend globally, and which alternatives remain. We develop the foundations of Algebraic Architecture Theory (AAT) from Atoms, typed primitive facts, and Laws, equations that objects must satisfy. A reading specifies what counts as structure and which operations and laws to preserve. The main reconstruction theorem identifies the category of full geometries and all their structure-preserving morphisms with an independently defined category of local models, up to equivalence. Objects are recovered up to isomorphism and morphisms between fixed endpoints uniquely. The theory addresses gluing, diagnosis, transport, classification of changes, and reconstruction. From finite Atom families we construct cores closed under operations and geometries with sites and coefficients. We give conditions under which a Cech obstruction detects the existence of a global state and, through comparison with repair semantics, a global repair. We compare diagnoses and give a finite criterion for uniform invariance given computable finite data. Transport along exact changes has a universal property and commutes with base change on exact pointed pullback squares. Comparisons of routes generated from the same square, finite comparison diagram, and geometry factor into an invertible comparison and an idempotent normalization. We characterize when observations determine comparison preservation and classify compatible lifts. Encodings of lens and protocol semantics preserve and reflect laws and recover semantics-preserving morphisms. Applications classify and count operation-preserving changes and extend morphisms uniquely from finite tables. Corresponding Lean declarations are listed in the appendix.

0.45

A Catalogue of Properties of Binary Relations: Entailments, Incompatibilities, and Independence Results

cs.LO math.LO ·2026-09-10 ·Magnus Boman
similarity 0.56
Abstract · 17 pages, 1 figure, 1 table

We study fifteen properties of binary relations that have established uses in modal logic, order and preference theory, and relation algebra. The organising question is pragmatic: once some properties of a relation are known, which further properties follow, which combinations force degeneracy, and which properties remain independent? We give a proved Horn basis of elementary and compound entailments, explicit countermodels for non-entailments, and a relation-algebraic translation of all fifteen properties. The modal discussion includes the usual Scott--Lemmon correspondences and the logic of transitive dense frames studied by Ghilardi and Mints. Exhaustive finite enumeration and targeted model search are used for discovery, while the catalogue is certified in Lean. A kernel-checked coverage calculation ranges over all 2^15 = 32,768 antecedent sets and all fifteen possible consequents. Its 51-rule Horn manifest is coupled definitionally to Lean proofs of semantic soundness, and its 49 witness rows are coupled definitionally to Lean-certified finite or infinite relations. Consequently, over non-empty domains, the Horn closure is complete for positive entailment among the fifteen selected properties, and the consistency classification is complete for their positive combinations.

0.26

Approximate Functional Dependencies---Implication Problem Revisited

cs.LO cs.DB ·2026-08-17 ·Nicolas Fröhlich, Matilda Häggblom, Åsa Hirvonen, Minna Hirvonen
similarity 0.56
Abstract · 11 pages

Functional dependencies are an important and well-studied class of database constraints that correspond to a notion expressed by dependence atoms in team logic. In practice, data often contain errors, so in some cases it might be useful to allow the database to have a small number of tuples that violate the desired dependency. Väänänen (2017) studied the axiomatisation of a notion of approximate dependence that specifies for each dependence atom how much of the database can be disregarded. We demonstrate that the interaction of approximate dependence atoms is more complicated than previously thought in the sense that there is a semantic consequence that is not captured by the inference rules introduced before. We show that Väänänen's axiomatisation is still complete in the restricted case of unary dependencies. We also consider the complexity of model checking for approximate dependence: it is NP-complete for disjunctions of two atoms and LOGSPACE-hard for individual atoms.

0.21

Undecidability of Reachability for Constraint Automata

cs.FL ·2026-10-11 ·Jakub Michaliszyn
theoryhot direction similarity 0.55
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

Efficient Nominal Automata Computation with Strong Nominal Sets

cs.FL ·2026-11-17 ·Hiroya Fujinami
hot direction similarity 0.54
Abstract · 47 pages

Nominal automata and register automata are expressively equivalent models of computation over infinite alphabets, yet an algorithmic gap separates them in practice: dedicated algorithms decide language equivalence of deterministic register automata in polynomial time by working orbit-wise, while general-purpose nominal-computation tools that rely on SMT solvers hide the orbit structure and degrade rapidly even on small instances. We trace this gap to non-trivial local symmetries in nominal sets and observe that the configuration spaces of register automata correspond to strong nominal sets, whose elements carry only trivial local symmetries. We characterize strong nominal sets categorically, consolidating known and new equivalences, and derive a constraint-free array representation of orbit-finite strong nominal sets and equivariant maps; we further prove the existence of projective covers, guaranteeing that every nominal set admits a strong approximation preserving both orbit count and dimensions, computable for quotients of strong nominal sets. Building on these results, we develop concrete algorithms for language equivalence, minimization, and active learning, bridging the algorithmic gap for equivalence (in polynomial time for a fixed alphabet dimension) and extending the orbit-wise approach to minimization and learning. Finally, our implementation Namae, based on the array representation, outperforms existing nominal-computation tools and, at scale, stays within a small constant factor of a dedicated register-automaton equivalence tool.

0.40