Complexity operator classification in regular rewriting systems

C. Chabaud

LIP6 1998/027: Rapport de Recherche LIP6 / LIP6 research reports
23 pages - Juin/June 1998 - Document en anglais.

PostScript : 118 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Calcul Formel

Titre français : Classification des opérateurs selon la complexité dans un système de réécriture régulier
Titre anglais : Complexity operator classification in regular rewriting systems

Résumé : Un système de réécriture régulier est caractérisé par une matrice de représentation dont l'analyse algébrique permet d'évaluer la complexité moyenne des opérateurs du système. L'analyse de la valeur propre dominante de la matrice de représentation et de son graphe orienté dégage une classification des opérateurs du système en s'appuyant sur des résultats d'analyse de singularité.

Abstract : Regular tree rewriting systems identify with a representation matrix from which we make an algebraic analysis in order to evaluate the average complexity of all the system operators. Then, a joint analysis of the dominating eigenvalue and the directed graph of the representation matrix gives a classification of the system operators using the results of singularity analysis as mathematical background.

Mots-clés : réécriture, fonctions algébriques, matrices non négatives, dérivation formelle

Key-words : rewriting, algebraic functions, nonnegative matrices, formal differentiation

Publications internes LIP6 1998 / LIP6 research reports 1998

Responsable Éditorial / Editor
webmaster@lip6.fr