zbMATH — the first resource for mathematics

The rank of a formal tree power series. (English) Zbl 0537.68053
A formal power series on trees is a mapping from a free algebra \(T_{\Sigma}\) into a field K; recall that \(\Sigma\) is a set of symbols of functions \(\Sigma =\Sigma_ 0\cup...\cup \Sigma_ n\cup...\) and that \(T_{\Sigma}\) (the set of trees) is defined inductively by: \(\Sigma_ 0\subset T_{\Sigma};\) if \(f\in \Sigma_ n\) and \(t_ 1,...,t_ n\in T_{\Sigma},\) then \(f(t_ 1,...,t_ n)\in T_{\Sigma}.\) A representation of \(T_{\Sigma}\) is a family of mappings \(\mu_ n:\Sigma_ n\to {\mathcal L}(V^ n,V),\) the space of all n-linear mappings \(V^ n\to V,\) where V is a finite-dimensional vector space over K. The mapping \(\mu_ 0:\Sigma_ 0\to V (\simeq {\mathcal L}(V^ 0,V))\) extends uniquely to a mapping \(T_{\Sigma}\to V\) through the formula \(\mu(f(t_ 1,...,t_ n))=\mu_ n(f)(\mu t_ 1,...,\mu t_ n).\) If \(\lambda:V\to K\) is linear, then the formal power series \(t\mapsto \lambda {\mathbb{O}}\mu(f)\) is called recognizable. The authors give a Hankel-like characterization of recognizable series. Let \(\kappa\) be a new variable and define \(\Sigma '\!_ 0=\Sigma_ 0\cup \kappa,\) T’\({}_{\Sigma}\) the resulting free algebra and \(P_{\Sigma}\) the subset of \(T'_{\Sigma}\) consisting of trees with exactly one occurrence of \(\kappa\). \(P_{\Sigma}\) acts naturally on \(T_{\Sigma}\) by substitution: \(T_{\Sigma}\times P_{\Sigma}\to T_{\Sigma}, (t,\tau)\mapsto t\tau.\) If S is a formal power series, \(S=\sum_{t\in T_{\Sigma}}(S,t)t,\) and if \(t\in T_{\Sigma}, \tau \in P_{\Sigma},\) define \(t^{-1}S=\sum_{\tau \in P_{\Sigma}}(S,t\tau)\tau, S\tau^{- 1}=\sum_{t\in T_{\Sigma}}(S,t\tau)t.\) Then S is recognizable iff the set of \(t^{-1}S (t\in T_{\Sigma})\) has finite rank in \(K^{P_{\Sigma}},\) iff these to \(S\tau^{-1}(\tau \in P_{\Sigma})\) has finite rank in \(K^{T_{\Sigma}}\). In this case, these ranks are equal.
Reviewer: Ch.Reutenauer

68Q70 Algebraic theory of languages and automata
17A50 Free nonassociative algebras
Full Text: DOI
[1] Berstel, J.; Reutenauer, C., Recognizable formal power series on trees, Theoret. comput. sci., 18, 115-148, (1982) · Zbl 0485.68077
[2] Fliess, M., Matrices de Hankel, J. math. pures appl., 53, 197-222, (1974) · Zbl 0315.94051
[3] Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, (1978), Springer Berlin · Zbl 0377.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.