Skip to main content

Research Repository

Advanced Search

Freeness properties of weighted and probabilistic automata over bounded languages

Bell, Paul C.; Chen, Shang; Jackson, Lisa

Freeness properties of weighted and probabilistic automata over bounded languages Thumbnail


Authors

Shang Chen

Lisa Jackson



Abstract

There has been much research into freeness properties of finitely generated matrix semigroups under various constraints, such as the dimensions of the generator matrices and the semiring over which the matrices are defined. Most freeness problems have been shown to be undecidable starting from dimension three, even for upper-triangular matrices over the natural numbers. There are many open problems still remaining in dimension two. A recent paper has also investigated freeness properties of bounded languages of matrices, which are matrices from a set M*1 M*2· · · M*k ? Fn×n for some semiring F and a fixed value k ? N>0, where matrices M1, . . . , Mk are given [1]. We consider a notion of freeness and ambiguity for scalar reachability problems in matrix semigroups and bounded languages of matrices. Scalar reachability concerns the set {?TMt |M ? S}, where ?, t ? F n are vectors and S ? F n×n is a finitely generated matrix semigroup. Ambiguity and freeness problems are defined in terms of the uniqueness of factorizations for each scalar. Such problems have also been studied in connection to formal power series. We show various undecidability results and their connections to weighted and probabilistic finite automata.

Citation

Bell, P. C., Chen, S., & Jackson, L. (2019). Freeness properties of weighted and probabilistic automata over bounded languages. Information and Computation, 269, -. https://doi.org/10.1016/j.ic.2019.104440

Journal Article Type Article
Acceptance Date Jul 30, 2017
Online Publication Date Aug 26, 2019
Publication Date 2019-12
Publicly Available Date May 30, 2023
Journal Information and Computation
Print ISSN 0890-5401
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 269
Article Number 104440
Pages -
DOI https://doi.org/10.1016/j.ic.2019.104440
Publisher URL https://www.sciencedirect.com/science/article/pii/S0890540119300574?via%3Dihub

Files






You might also like



Downloadable Citations