Determinisability of unary weighted automata over the rational numbers
type: Item
instance of: scholarly article
title: Determinisability of unary weighted automata over the rational numbers
zbMATH Open document ID: 1490.68127
author: Peter Kostolányi
published in: Theoretical Computer Science
publication date: 2021-12-01T00:00:00Z
review text: The contribution shows that the sequentiality problem for unary weighted finite automata (WFA) over the rational numbers is decidable and that an equivalent sequential WFA can effectively be constructed in the positive case. A weighted finite automaton is essentially a finite-state automaton in which each transition additionally carries a weight. The weights are rational numbers in this contribution and are multiplied along the several transitions that constitute a run, and the weights of multiple runs for the same input are added up. The sequentiality problem asks for a given WFA whether there exists an equivalent sequential (or deterministic) WFA in which for each state and input symbol there exists a unique (nonzero-weighted) transition. Finally, the WFA is unary if the input alphabet has at most one symbol. The sequentiality problem was only solved in very special cases for unary WFA. The author develops the notion of the characteristic polynomial for a given WFA. It is derivable from a minimal WFA for the same computed mapping. Such a minimal WFA can efficiently be derived easily using existing algorithms. It is demonstrated that the characteristic polynomial is invariant under changes of the basis, so the characteristic polynomial is actually unique for the computed function (and independent of the chosen minimal WFA computing it). It is demonstrated that the characteristic polynomial needs to have one of two special shapes for the given WFA to be determinizable. Essentially, the characteristic polynomial needs to be factorized and all its nonzero roots need to be simple. If the decision algorithm returns that the WFA is determinizable then an equivalent deterministic WFA can be determined efficiently as well. The contribution includes a detailed complexity analysis and several examples illustrate the decision as well as the construction algorithms. Overall, the paper is excellently written and provides exactly the right amount of detail and intuition. The exa…
reviewed by: Andreas Maletti
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7437228
zbMATH Keywords: deterministic weighted automaton
zbMATH Keywords: sequential weighted automaton
zbMATH Keywords: reduced representation
zbMATH Keywords: characteristic polynomial
zbMATH Keywords: cyclotomic polynomial
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.11.002
OpenAlex ID: W3213392216
cites work: Q4449534
cites work: Calculating cyclotomic polynomials
cites work: Q4888749
cites work: Automata, Languages and Programming
cites work: Conjugacy and Equivalence of Weighted Automata and Functional Transducers
cites work: Noncommutative rational Pólya series
cites work: Q3056218
cites work: Q4432295
cites work: Algebraic Codes for Data Transmission
cites work: Q3900997
cites work: Finite automata and unary languages
cites work: Determinization of weighted finite automata over strong bimonoids
cites work: Crisp-determinization of weighted tree automata over additively locally finite and past-finite monotonic strong bimonoids is decidable
cites work: Semirings and Formal Power Series
cites work: Handbook of weighted automata
cites work: Weighted automata
cites work: Efficient computation of the characteristic polynomial
cites work: Q4423053
cites work: Q4679023
cites work: Crisp-determinization of weighted tree automata over strong bimonoids
cites work: La finitude des représentations linéaires des semi-groupes est decidable
cites work: The Generalized Vandermonde Matrix
cites work: Fast algorithms for the characteristic polynomial
cites work: Q4507789
cites work: Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
cites work: Q3431481
cites work: Sequential?
cites work: On finite semigroups of matrices
cites work: On Landau's function g(n)
cites work: Fuzzy Languages
cites work: Approximate formulas for some functions of prime numbers
cites work: Q3644388
cites work: Rational and Recognisable Power Series
cites work: On the definition of a family of automata
cites work: Gaussian elimination is not optimal
cites work: Modern computer algebra
DOI: 10.1016/J.TCS.2021.11.002
description: scientific article; zbMATH DE number 7437228