CS Paper Radar

Reliability-Aware Z-Grammars and Z-Automata over a Credible-Grade Semiring

Sherzod Turaev, Nor Haniza Sarmin, Wan Heng Fong

cs.FL cs.LO ·submitted 2026-11-05 10:19 UTC · v1
theory

Abstract

Fuzzy grammars and weighted automata usually attach to each word a single grade, which records how strongly the word is generated but not how far that record can be trusted. We study weighted grammars and finite automata whose weights are scalar grade-reliability pairs inspired by Z-numbers. Sequential composition multiplies both components, while aggregation selects a derivation by its credible grade, the product of grade and reliability, with ties resolved by grade. On the canonical carrier, in which the weights of zero grade or zero reliability are identified with zero, the resulting structure is a commutative selective semiring, isomorphic to a subsemiring of a lexicographically ordered product, and its credible-grade projection is a homomorphism onto the Viterbi semiring. We compare several alternative combination rules and identify the carriers on which the relevant algebraic laws hold. Standard results on weighted automata then yield a rational characterization and closure properties. We prove that positive credible-grade cuts and selected-run reliability filters of finite automata are regular and effectively constructible for rational weights and thresholds, and we exhibit distinctions that the scalar projection cannot see: a reliability filter that no scalar reweighting of the same one-state automaton implements, nonmonotonicity under the addition of runs, and an unambiguous automaton with no deterministic equivalent although its scalar projection is deterministic. A count-based example illustrates an attestation penalty for grammar rules. The construction concerns scalar pairs, and its extension to arbitrary fuzzy-valued Z-numbers remains open.

Comment
35 pages, 7 figures, 3 tables

Closest papers

Nearest neighbours by meaning across the whole index.

The Value Generating Power of Weighted Tree Automata with Initial Algebra Semantics

cs.FL ·2026-08-25 ·Manfred Droste, Zoltán Fülöp, Andreja Tepavčević, Heiko Vogler
published similarity 0.62
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the generating power of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings) and the question under which conditions the weighted tree automata can produce only finitely many values. We show that there exists a right-distributive strong bimonoid which is bi-locally finite but not locally finite. We also show that if the ranked alphabet contains a symbol with rank at least two, then for any finitely generated strong bimonoid, weighted tree automata can generate, via their initial algebra semantics, all elements of the strong bimonoid. As a consequence of these results, for bi-locally finite right-distributive strong bimonoids which are not locally finite, weighted tree automata can generate infinitely many values, provided that the input ranked alphabet contains a symbol with rank at least two. This is in sharp contrast to the setting of weighted string automata, which can generate only finitely many values. As a further consequence, for any finitely generated semiring, there exists a weighted tree automaton which generates, via its run semantics, all elements of the semiring.

0.72

From Transformers to Weighted Automata: Towards the Verification of Large Language Models

cs.FL cs.LG ·2026-10-03 ·Smayan Agarwal, Aslah Ahmad Faizi, Shobhit Singh, Aalok Thakkar
published similarity 0.57
Abstract

Large language models (LLMs) are increasingly deployed in safety-critical settings, yet their black-box nature makes it difficult to provide formal guaranties about their behavior. Existing verification approaches rely primarily on empirical probing and testing, leaving open the question of how to reason rigorously about general-purpose trans- former architectures. In this work, we establish a principled bridge between transformers and weighted automata, a classical model from formal language theory. This connection enables us to transfer verification tools from automata the- ory to the analysis of LLMs. Our contributions are twofold: First, we develop a formal correspondence between transformer architectures and weighted automata over reals, showing how distributional properties of LLMs can be captured within this framework. Second, we introduce an identity testing algorithm for weighted automata that provides a statis- tical method for distinguishing whether two stochastic models define the same distribution up to a tolerance threshold. This work provides the first formal bridge between modern neural se- quence models and classical automata theory, clarifying both the poten- tial and the computational challenges for rigorous LLM verification.

0.34

Weighted Alternating Tree Automata

cs.FL ·2026-08-25 ·Olle Torstensson
published similarity 0.57
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We define weighted alternating tree automata — a generalization of weighted (non-alternating) tree automata, (unweighted) alternating tree automata, and weighted alternating (string) automata — over commutative semirings. We study their expressive power, and show that it is equivalent to that of weighted tree automata exactly when the employed semiring is locally finite. In our main result, we characterize the class of weighted tree languages defined by weighted alternating tree automata as the closure of the recognizable weighted tree languages under inverse tree homomorphisms.

0.46

General semiring conditions for weighted L* termination

cs.FL cs.LO ·2026-10-30 ·Noah Bertram, Daniel Luckhardt, Alexandra Silva
similarity 0.56
Abstract · 22 pages

Weighted automata learning has been well-studied over (semi)rings which have a dimension theory. In this work, we investigate active learning for weighted automata over semirings that lack such a structure. We first show that the principal ideal domain variant of the L* algorithm also terminates for a larger class of semirings containing Noetherian semirings, commutative rings, and bounded distributed lattices. We then present a variant of this algorithm for learning deterministic weighted automata, and prove that this algorithm terminates for commutative semirings.

0.24

Shortest Synchronizing Words on Product Automata

cs.FL ·2026-11-06 ·Henning Fernau, Igor Rystsov
similarity 0.55
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

Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier

cs.FL cs.CLcs.PL ·2026-10-16 ·Nicklas Nidhögg
theory similarity 0.51
Abstract · 39 pages, 1 figure, 2 tables. v2: revises the introduction to credit existing exact procedures (Koo et al. for masks, Berglund et al. for BP…

A segmentation policy assigns to each byte string at most one segmentation into tokens. Call it finitely verifiable when a finite automaton over marked strings, bytes paired with boundary bits, accepts exactly the policy's own segmentations. The automaton judges a proposed segmentation and need not compute one. From a supplied verifier the paper gives constructive decisions for four questions, whether a window certifies a token boundary, whether the boundary gap is bounded, whether a mask can keep generation from dead-ending, and whether two policies are equivalent. The last three specialize limitedness, co-accessibility and the equivalence of single-valued transducers. The first refines the synchronizing cut of code theory, and two more ask whether a certified cut, or the cuts of an inventory, let each piece scan alone. The class sits strictly between the online-scannable policies and those with regular domains, and online scannability is decidable in polynomial time through Choffrut's theorem. Markings are length-preserving, so the class is exactly the rational segmentation policies, a normal form rather than a restriction. The class is closed under four pipeline operations, composition over a labeled stage, restriction to a regular schema, splitting at character-class changes, and byte-fallback union of literal policies. Each composite inherits the six decisions, and certificates transfer between stages under four laws. Under rational, unifilar, almost surely stopping finite-state sources, each mass of the weighted section is an exact rational, and so is each rate where expected length is positive. Maximal-munch lexing, canonical byte-pair encoding and two-mode WordPiece instantiate the interface, and the munch library implements all six decisions. Every theorem carries an executable check, and every reported statistic is a program's own output.

0.24

Quantitative Verification of Infinite-State Networks

cs.FL cs.LOcs.PL ·2026-10-08 ·Dhruv Nevatia, David Basin
top venue similarity 0.50
Abstract · Accepted at POPL 2027. Full version with appendices, 46 pages, and 13 figures

Many network protocols and distributed systems combine recursion, unbounded local state, and quantitative behaviour such as cost, latency, or reliability. Existing decidability results for networks of pushdown systems are largely qualitative, and do not extend to quantitative analyses, which must jointly track traces and weights. We present a framework for the quantitative verification of acyclic networks of weighted pushdown systems. Finitely summarising a recursive network component requires collapsing the infinite family of runs obtained by pumping its nested loops, and doing so exactly, rather than by over-approximation, is a standing difficulty. We give a class of weight domains where this is possible: pumping semirings, those in which the weights accumulated by such a family collapse to a closed form; informally, the domain must be unable to count iterations. The class admits domains with infinite ascending chains, such as the arctic semiring and downward-closed languages. Over these, we give a terminating saturation algorithm computing quantitative reachability exactly, resting on two ideas: segment tree algebras, a compositional representation of runs, and thermal extensions, which symbolically separate accelerated weights so that further acceleration remains exact. We use this to compute upward and downward closures of context-free languages uniformly, and to lift the algorithm to acyclic networks over "thin" pumping semirings, yielding the first quantitative safety and reachability analyses for networks of pushdown systems.

0.44

Formal Grammars and Generating Functions: From Algebraic Structure to Non-Algebraic and Non-Derivable Series

cs.FL ·2026-10-22 ·Zhijun Wang
theory similarity 0.50
Abstract

This paper investigates how the algebraic and analytic properties of ordinary length generating functions constrain the grammatical and computational complexity of formal languages. We review the Chomsky-Schutzenberger representation, DSV translations for unambiguous context-free grammars, and their stack-indexed extensions, distinguishing finite algebraic systems from more general constructions. Examples and a diagonal argument demonstrate that even a rational generating function need not determine a language's grammatical class. Our central computability result establishes that, for a recursively enumerable language, computability of its length-counting sequence is equivalent to decidability of membership. Consequently, if a recursively enumerable language has a D-finite length generating function over Q(z), it is decidable; equivalently, undecidable recursively enumerable languages cannot have D-finite length generating functions. We then examine coefficient growth and singularities through Pringsheim's theorem, the Polya-Carlson dichotomy, Hadamard gaps, and Siegel G-functions. The resulting picture is asymmetric: analytic properties provide useful one-way constraints on language computability, but length enumeration loses too much information to determine grammatical or computational complexity without additional assumptions.

0.12