×

zbMATH — the first resource for mathematics

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

MSC:
68Q45 Formal languages and automata
05C05 Trees
08B20 Free algebras
PDF BibTeX XML Cite
Full Text: DOI
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
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.