Nonnegative companion matrices and star-height of \(\mathbb{N}\)-rational series
type: Item
instance of: scholarly article
title: Nonnegative companion matrices and star-height of \(\mathbb{N}\)-rational series
zbMATH Open document ID: 0908.12001
DOI: 10.1016/S0304-3975(96)00106-5
author: Frédérique Bassino
published in: Theoretical Computer Science
publication date: 1998-07-22T00:00:00Z
review text: A formal power series is called \(\mathbb{N}\)-rational if it can be obtained from polynomials with coefficients in \(\mathbb{N}\) by using sums, Cauchy products, and star operations \(P^*\), where for \(P\) such that \(P(0)= 0\), \[ P^*= {1\over 1-P}= \sum_{n\geq 0} P^n. \] The star-height of such a series is the minimal number of star operations needed to construct it as above. It is known that the star-height of any \(\mathbb{N}\)-rational series in one variable is at most 2 (see [\textit{A. Salomaa} and \textit{M. Soittola}, Automata-theoretic aspects of formal power series, Springer (1978; Zbl 0377.68039) and \textit{T. Katayama}, \textit{M. Okamoto} and \textit{H. Enomoto}, Inf. Control 36, 85-101 (1978; Zbl 0378.68042)]). Since the \(\mathbb{N}\)-rational series of star-height \(0\) are exactly the polynomials, an interesting question is to characterize the \(\mathbb{N}\)-rational series of star-height \(1\). The author proves the nice following result: If an \(\mathbb{N}\)-rational series has star-height \(1\), then its real positive roots \(\lambda_i\) are such that \(\forall i\exists k_i\) such that \(\lambda^{k_i}_i\) is a Perron number that has no positive real algebraic conjugate. This condition is also sufficient if the series has a dominating root. (A Perron number is a real algebraic number \(>1\) strictly greater than all the moduli of its conjugates. The author proposes the term of Handelman numbers for Perron numbers satisfying the extra condition above).
Mathematics Subject Classification ID: 12D10
Mathematics Subject Classification ID: 11R06
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 15B48
zbMATH DE Number: 1177589
zbMATH Keywords: formal power series
zbMATH Keywords: star-height
zbMATH Keywords: \(\mathbb{N}\)-rational series
zbMATH Keywords: Perron number
zbMATH Keywords: Handelman numbers
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
cites work: Star-height of an N-rational series
cites work: Q3994777
cites work: Q4281308
cites work: Transition graphs and the star-height of regular events
cites work: Q3254327
cites work: Q4037008
cites work: Characterization of the structure-generating functions of regular sets and the DOL growth functions
cites work: On the Forms of the Predicates in the Theory of Constructive Ordinals
cites work: The entropies of topological Markov shifts and a related class of algebraic integers
cites work: Q4039989
cites work: On positive matrices
cites work: Inversion height in free fields
cites work: Q4155837
cites work: On the definition of a family of automata
cites work: Q5626549
cites work: Positive rational sequences
full work available at URL: s0304-3975(96)00106-5
OpenAlex ID: W2025389360
Recommended article: Another proof of Soittola's theorem
Recommended article: Star-height of an N-rational series
Recommended article: Automata and the arithmetic of formal power series
Recommended article: \(\mathbb Z\)-rationality of a certain class of formal series
Recommended article: The rationality of the Poincaré series associated to the p-adic points on a variety
Recommended article: Diagonalization and Rationalization of algebraic Laurent series
Recommended article: Q5617693
Recommended article: Inverse polynomial expansions of Laurent series
Recommended article: Q4277616
Recommended article: Sur une propriété arithmétique de quelques fonctions entières.
description: scientific article; zbMATH DE number 1177589