Bell, PC, Chen, S and Jackson, LM (2019) Freeness Properties of Weighted and Probabilistic Automata over Bounded Languages. Information and Computation. ISSN 0890-5401

Preview

Text BelCheJac16revise2.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (385kB) | Preview

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. 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 of scalar values computable from multiplying a fixed row vector by a matrix from a finately generated semigroup and then multiplying by a fixed column vector, of appropriate size. 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.

Item Type:	Article
Uncontrolled Keywords:	08 Information And Computing Sciences
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	Computer Science & Mathematics
Publisher:	Elsevier
Date Deposited:	25 Sep 2017 11:00
Last Modified:	04 Sep 2021 11:11
DOI or ID number:	10.1016/j.ic.2019.104440
Editors:	Martin-Vide, C and Truthe, B
URI:	https://researchonline.ljmu.ac.uk/id/eprint/7185

View Item