×

Représentations matricielles des séries d’arbre reconnaissables. (Matrix representations of series on recognizable trees). (French) Zbl 0689.68099

We characterize recognizable formal series on trees by means of matrix representations. Further, we prove that the image of such a representation with minimum dimension is isomorphic to the syntactic \({\mathbb{K}}-\Sigma\)-algebra of the induced series. Finally, we show that two minimal matrix represenations of the same series, are “similar”.

MSC:

68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
17A50 Free nonassociative algebras
08B20 Free algebras
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. J. BERSTEL et C. REUTENAUER, Recognizable Formal Power Series on Trees, Theoret. Comput. Sci., vol. 18, 1982, p. 115-148. Zbl0485.68077 MR652467 · Zbl 0485.68077 · doi:10.1016/0304-3975(82)90019-6
[2] 2. S. BOZAPALIDIS et O. LOUSCOU-BOZAPALIDOU, The Rank of a Formal Tree Power Series, Theoret. Comput. Sci., vol. 27, 1983, p. 211-215. Zbl0537.68053 MR742285 · Zbl 0537.68053 · doi:10.1016/0304-3975(83)90100-7
[3] 3. C. REUTENAUER, Séries formelles et algèbres syntactiques, Journal of Algebra, vol. 66, 1980, p. 448-483. Zbl0444.68075 MR593604 · Zbl 0444.68075 · doi:10.1016/0021-8693(80)90097-6
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.