The (left) linear hull of a weighted automaton over a field is a topological invariant. If the automaton is minimal, the linear hull can be used to determine whether or not the automaton is ...equivalent to a deterministic one. Furthermore, the linear hull can also be used to determine whether the minimal automaton is equivalent to an unambiguous one. We show how to compute the linear hull, and thus prove that it is decidable whether or not a given automaton over a number field is equivalent to a deterministic one. In this case we are also able to compute an equivalent deterministic automaton. We also show the analogous decidability and computability result for the unambiguous case. Our results resolve a problem posed in a 2006 survey by Lombardy and Sakarovitch.
In this note, we extend results about unique \(n^{\textrm{th}}\) roots and cancellation of finite disconnected graphs with respect to the Cartesian, the strong and the direct product, to the rooted ...hierarchical products, and to a modified lexicographic product. We show that these results also hold for graphs with countably many finite connected components, as long as every connected component appears only finitely often (up to isomorphism). The proofs are via monoid algebras and generalized power series rings.
If \(H\) is a monoid and \(a=u_1 \cdots u_k \in H\) with atoms (irreducible elements) \(u_1, \ldots, u_k\), then \(k\) is a length of \(a\), the set of lengths of \(a\) is denoted by \(\mathsf ...L(a)\), and \(\mathcal L(H)=\{\,\mathsf L (a) \mid a \in H \,\}\) is the system of sets of lengths of \(H\). Let \(R\) be a hereditary Noetherian prime (HNP) ring. Then every element of the monoid of non-zero-divisors \(R^\bullet\) can be written as a product of atoms. We show that, if \(R\) is bounded and every stably free right \(R\)-ideal is free, then there exists a transfer homomorphism from \(R^{\bullet}\) to the monoid \(B\) of zero-sum sequences over a subset \(G_{\textrm{max}}(R)\) of the ideal class group \(G(R)\). This implies that the systems of sets of lengths, together with further arithmetical invariants, of the monoids \(R^{\bullet}\) and \(B\) coincide. It is well-known that commutative Dedekind domains allow transfer homomorphisms to monoids of zero-sum sequences, and the arithmetic of the latter has been the object of much research. Our approach is based on the structure theory of finitely generated projective modules over HNP rings, as established in the recent monograph by Levy and Robson. We complement our results by giving an example of a non-bounded HNP ring in which every stably free right \(R\)-ideal is free but which does not allow a transfer homomorphism to a monoid of zero-sum sequences over any subset of its ideal class group.
We associate lattices to the sets of unions and intersections of left and right quotients of a regular language. For both unions and intersections, we show that the lattices we produce using left and ...right quotients are dual to each other. We also give necessary and sufficient conditions for these lattices to have maximal possible complexity.
We enumerate all orders in definite quaternion algebras over number fields with the Hermite property; this includes all orders with the cancellation property for locally free modules.
We study direct-sum decompositions of torsion-free, finitely generated modules over a (commutative) Bass ring \(R\) through the factorization theory of the corresponding monoid \(T(R)\). Results of ...Levy-Wiegand and Levy-Odenthal together with a study of the local case yield an explicit description of \(T(R)\). The monoid is typically neither factorial nor cancellative. Nevertheless, we construct a transfer homomorphism to a monoid of graph agglomerations--a natural class of monoids serving as combinatorial models for the factorization theory of \(T(R)\). As a consequence, the monoid \(T(R)\) is transfer Krull of finite type and several finiteness results on arithmetical invariants apply. We also establish results on the elasticity of \(T(R)\) and characterize when \(T(R)\) is half-factorial. (Factoriality, that is, torsion-free Krull-Remak-Schmidt-Azumaya, is characterized by a theorem of Levy-Odenthal.) The monoids of graph agglomerations introduced here are also of independent interest.
A (noncommutative) P\'olya series over a field $K$ is a formal power series
whose nonzero coefficients are contained in a finitely generated subgroup of
$K^\times$. We show that rational P\'olya ...series are unambiguous rational
series, proving a 40 year old conjecture of Reutenauer. The proof combines
methods from noncommutative algebra, automata theory, and number theory
(specifically, unit equations). As a corollary, a rational series is a P\'olya
series if and only if it is Hadamard sub-invertible. Phrased differently, we
show that every weighted finite automaton taking values in a finitely generated
subgroup of a field (and zero) is equivalent to an unambiguous weighted finite
automaton.
A classical result of Claborn states that every abelian group is the class group of a commutative Dedekind domain. Among noncommutative Dedekind prime rings, apart from PI rings, the simple Dedekind ...domains form a second important class. We show that every abelian group is the class group of a noncommutative simple Dedekind domain. This solves an open problem stated by Levy and Robson in their recent monograph on hereditary Noetherian prime rings.
A multivariate, formal power series over a field \(K\) is a Bézivin series if all of its coefficients can be expressed as a sum of at most \(r\) elements from a finitely generated subgroup \(G \le ...K^*\); it is a Pólya series if one can take \(r=1\). We give explicit structural descriptions of \(D\)-finite Bézivin series and \(D\)-finite Pólya series over fields of characteristic \(0\), thus extending classical results of Pólya and Bézivin to the multivariate setting.
PDF