Notes on Equivalence and Minimization of Weighted Automata

Stefan Kiefer

RECORD

Notes on Equivalence and Minimization of Weighted Automata

Stefan Kiefer

Formal Languages and Automata Theory · Submitted 2 Sep 2020

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim This set of notes re-proves known results on weighted automata (over a field, also known as multiplicity automata).

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 5,976 input tokens.

What the abstract itself states, as probabilities: claims first 0.01 · states limitation 0.95 · human participants 0.01 · controlled comparison 0.01 · randomized assignment 0.01 · states quantitative result 0.03 · compares with prior results 0.16 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

This set of notes re-proves known results on weighted automata (over a field, also known as multiplicity automata). The text offers a unified view on theorems and proofs that have appeared in the literature over decades and were written in different styles and contexts. None of the results reported here are claimed to be new. The content centres around fundamentals of equivalence and minimization, with an emphasis on algorithmic aspects. The presentation is minimalistic. No attempt has been made to motivate the material. Weighted automata are viewed from a linear-algebra angle. As a consequence, the proofs, which are meant to be succinct, but complete and almost self-contained, rely mainly on elementary linear algebra.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	This set of notes re-proves known results on weighted automata (over a field, also known as multiplicity automata).	contribution 0.65	0.72	0.13	asserted 1.00
s1	The text offers a unified view on theorems and proofs that have appeared in the literature over decades and were written in different styles and contexts.	contribution 0.79	0.68	0.07	asserted 1.00
s2	None of the results reported here are claimed to be new.	limitation 0.99	0.34	0.11	asserted 0.99
s3	The content centres around fundamentals of equivalence and minimization, with an emphasis on algorithmic aspects.	contribution 0.75	0.39	0.13	asserted 1.00
s4	The presentation is minimalistic.	method 0.50	0.72	0.03	asserted 1.00
s5	No attempt has been made to motivate the material.	limitation 0.99	0.88	0.02	asserted 1.00
s6	Weighted automata are viewed from a linear-algebra angle.	method 0.97	0.61	0.05	asserted 1.00
s7	As a consequence, the proofs, which are meant to be succinct, but complete and almost self-contained, rely mainly on elementary linear algebra.	method 0.98	0.71	0.10	asserted 1.00

What kind of paper the classifier reports this is: review 0.86 · evidence from proof or derivation 0.91.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

This set of notes re-proves known results on weighted automata (over a field, also known as multiplicity automata). The text offers a unified view on theorems and proofs that have appeared in the literature over decades and were written in different styles and contexts. None of the results reported here are claimed to be new. The content centres around fundamentals of equivalence and minimization, with an emphasis on algorithmic aspects. The presentation is minimalistic. No attempt has been made to motivate the material. Weighted automata are viewed from a linear-algebra angle. As a consequence, the proofs, which are meant to be succinct, but complete and almost self-contained, rely mainly on elementary linear algebra.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Parameterized equivalence checking of quantum circuit generators via weighted automata
quant-ph 2026-11 accept novelty 8.0 of 10

A method that uses weighted automata (matrix product operators) to verify equivalence of parameterized quantum circuit generators for all sizes and bit strings.
Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata
cs.FL 2025-11 conditional novelty 8.0 of 10

The minimum rank of a zero-one matrix monoid (unambiguous automaton) can be computed in NC² and O(mn⁴) time, and a minimum-rank matrix can be constructed faster than previously known.
Quantum Algorithms for Multivariable Polynomial Transformations: From Efficient Synthesis to Quantum Channel Transformations
quant-ph 2026-10 accept novelty 7.0 of 10

A compact rational description of a noncommutative multivariable polynomial suffices to build a near-optimal quantum circuit implementing it, with an exact D-query construction for row-block inputs.
A Decision Procedure for Probabilistic Kleene Algebra with Angelic Nondeterminism
cs.FL 2025-07 conditional novelty 7.0 of 10

The equational theory of probabilistic Kleene algebra with angelic nondeterminism is decidable via a Gröbner basis procedure on a forward ideal.

How the literature uses it

3 arXiv papers cite this in 11 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 6 sentences without a confident label

Uses its method or tool 1 paper

Using the technique from [ref] (see [ref] for a clearer explanation), for each $a ∈Σ$ one can compute[In [ref] only membership in $$ is claimed, but the bottleneck computations are matrix powering and rank computation, which can in fact be done in $DET ⊆^2$; see [ref] .

Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata · Computing the rank in NC2 · 0.87

Compares with it 1 paper

In support of this intuition, contrast polynomial-time algorithms for the equivalence problem on weighted automata over the ring of rationals [ref] with the PSPACE-completeness of equivalence for NFA [ref] .

Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata · Related work and discussion · 0.87

Cites it as background 2 papers

(The set $𝗌𝗉𝖺𝗇(𝖱𝖾𝖺𝖼𝗁)$ is known as the forward space of $A$; see, e.g., [ref] .

Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata · Certificates for Emptiness and Equivalence for weighted automata over fields · 0.99
Such “forward spaces” play an important role in weighted automata; see, e.g., [ref] .

Spectral and combinatorial methods for efficiently computing the rank of unambiguous finite automata · Maximal pseudo-columns · 0.97

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.