Recognizable formal power series on trees. (English) Zbl 0485.68077

Berstel, J.; Reutenauer, C.

Theor. Comput. Sci. 18, 115-148 (1982).

MSC:

68Q45	Formal languages and automata
05C05	Trees
08B20	Free algebras

Keywords:

functions on trees; free magma; recognizable function; algebraic noncommutative formal power series; algebricity of enumerating functions on trees; pumping lemma for recognizable functions

References:

[1]	Arnold, A., Systèmes d’équations dans le magmoïde: ensembles rationnels et algébriques d’arbes, Thèse d’etat, (1977), Lille
[2]	Berstel, J.; Reutenauer, C., Séries formelles reconnaissables d’arbres et applications, 5ème colloque de Lille: LES arbres en algèbre et en programmation, 11-21, (1980) · Zbl 0522.68077
[3]	Brainerd, W.S., Tree-generating regular systems, Information and control, 14, 217-231, (1969) · Zbl 0169.31601
[4]	Chottin, L., Une preuve combinatoire de la formule de Lagrange à deux variables, Discrete math., 13, 215-224, (1975) · Zbl 0335.05013
[5]	Cobham, A., Representation of a word function as the sum of two functions, Math. systems theory, 11, 373-377, (1978) · Zbl 0394.68045
[6]	Cohn, P.M., Universal algebra, (1965), Wiley New York · Zbl 0141.01002
[7]	Cori, R., Un code pour LES graphes planaires et ses applications, Astérique, 27, (1975) · Zbl 0313.05115
[8]	Dauchet, M., Transductions de forĕts: bimorphismes de magmoïdes, Thèse d’etat, (1977), Lille · Zbl 0382.68062
[9]	Eilenberg, S., Automata, languages and machines, Vol. A, (1974), Academic Press New York · Zbl 0317.94045
[10]	Flajolet, P., Analyse d’algorithmes de manipulation d’arbres et de fichiers, Thèse d’etat, (1979), Paris IX
[11]	P. Flajolet, Private Communication.
[12]	Flajolet, P.; Steyaert, J.M., On the analysis of tree-matching algorithms, 5ème colloque de Lille: LES arbres en algèbre et en programmation, (1980) · Zbl 0434.68046
[13]	Jacob, G., Un théorème de factorisation des produits d’endomorphismes, J. algebra, 63, 389-412, (1980) · Zbl 0441.16002
[14]	Kemp, R., On the average stack size of regularly distributed binary trees, (), 340-355 · Zbl 0415.05019
[15]	Knuth, D.E., The art of computer programming, Vol. 3, (1973), Addison-Wesley New York · Zbl 0191.17903
[16]	Lilin, E., S-transducteurs de forěts, 3ème C.L.A.A.P., 189-206, (1979) · Zbl 0384.68057
[17]	Maibaum, T., Pumping lemmas for term languages, J. comput. system sci., 17, 319-330, (1978) · Zbl 0388.68071
[18]	Mongy, J., Closure of recognizable tree-languages under intersection and morphisms, 5ème colloque de Lille: LES arbres en algèbres et programmation, 135-149, (1980) · Zbl 0446.68067
[19]	Nivat, M., On the interpretation of recursive polyadic program schemes, Symposia math., 15, 255-281, (1975)
[20]	Paz, A.; Salomaa, A., Integral sequential word functions and growth equivalence of lindenmayer systems, Information and control, 23, 313-343, (1973) · Zbl 0273.68056
[21]	Reutenauer, C., An ogden-like iteration lemma for rational power series, Acta informat., 13, 189-197, (1980) · Zbl 0423.68033
[22]	Rosen, B., Tree-manipulating systems and church – rosser theorem, J. ACM, 20, 160-187, (1973) · Zbl 0267.68013
[23]	Salomaa, A.; Soittola, M., Automata-theoretic aspects of formal power series, (1978), Springer Berlin · Zbl 0377.68039
[24]	Schützenberger, M.P., On the definition of a family of automata, Information and control, 4, 245-270, (1961) · Zbl 0104.00702
[25]	Thatcher, J.W., Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, J. comput. system sci., 1, 317-322, (1967) · Zbl 0155.01802
[26]	Thatcher, J.W., Generalized sequential machine maps, J. comput. system sci., 4, 339-367, (1970) · Zbl 0198.03303
[27]	Thatcher, J.W.; Wright, J.B., Generalized finite automata theory with an application to a decision problem of second-order logic, Math. systems theory, 2, 57-81, (1968) · Zbl 0157.02201