{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:10:36Z","timestamp":1771024236457,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":177,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642638596","type":"print"},{"value":"9783642591266","type":"electronic"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/978-3-642-59126-6_1","type":"book-chapter","created":{"date-parts":[[2011,8,17]],"date-time":"2011-08-17T08:30:28Z","timestamp":1313569828000},"page":"1-68","source":"Crossref","is-referenced-by-count":142,"title":["Tree Languages"],"prefix":"10.1007","author":[{"given":"Ferenc","family":"G\u00e9cseg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus","family":"Steinby","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF02483826","volume":"13","author":"J Ad\u00e1mek","year":"1981","unstructured":"Ad\u00e1mek, J., Trnkov\u00e1, V.: Varietors and machines in a category. Algebra Universalis 13, (1981), 89\u2013132","journal-title":"Algebra Universalis"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/S0019-9958(71)90706-6","volume":"19","author":"A Aho","year":"1971","unstructured":"Aho, A., Ullman, J. D.: Translations on a context-free grammar. In formation Control 19 (1971), 439\u2013475","journal-title":"In formation Control"},{"key":"1_CR3","unstructured":"Aigrain, P., Nivat, M.: Suffix, prefix and maximal tree codes. In: [TrAL92], 21\u201339"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1016\/S0022-0000(75)80045-6","volume":"10","author":"S Alagi\u0107","year":"1975","unstructured":"Alagi\u0107, S.: Natural state transformations. J. Comput. Systems Sci. 10 (1975), 266\u2013307","journal-title":"J. Comput. Systems Sci."},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01190713","volume":"27","author":"J Almeida","year":"1991","unstructured":"Almeida, J.: On pseudovarieties, varieties of languages, filters of congruences, pseudo-identities and related topics. Algebra Universalis 27 (1991), 333\u2013350","journal-title":"Algebra Universalis"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0019-9958(68)90374-4","volume":"12","author":"MA Arbib","year":"1968","unstructured":"Arbib, M. A., Give\u2019on, Y.: Algebra automata I: parallel programming as a prolegomena to the categorical approach. Information Control 12 (1968), 331\u2013345","journal-title":"Information Control"},{"key":"1_CR7","first-page":"11","volume":"4","author":"MA Arbib","year":"1978","unstructured":"Arbib, M. A., Manes, E. G.: Tree transformations and the semantics of loop-free programs. Acta Cybern. 4 (1978), 11\u201317","journal-title":"Acta Cybern"},{"key":"1_CR8","first-page":"272","volume":"13","author":"A Arnold","year":"1980","unstructured":"Arnold, A.: Le th\u00e9or\u00e8 me transversale rationelle dans les langages d\u2019arbres. Math. Systems Theory 13 (1980), 272\u2013282","journal-title":"Math. Systems Theory"},{"issue":"3","key":"1_CR9","first-page":"5","volume":"10","author":"A Arnold","year":"1976","unstructured":"Arnold, A., Dauchet, M.: Transductions de for\u00eats reconnaissables monadiques. For\u00eats cor\u00e9guli\u00e8res. RAIRO Informat. Th\u0107or. 10 (1976), No. 3, 5\u201328","journal-title":"For\u00eats cor\u00e9guli\u00e8res. RAIRO Informat.Th\u00e9or"},{"key":"1_CR10","first-page":"74","volume-title":"Bi-transductionsde for\u00eats. Automata, Lan-guages, and Programming (Proc. Conf. 1976)","author":"A Arnold","year":"1976","unstructured":"Arnold, A., Dauchet, M.: Bi-transductions de for\u00eats. Automata, Lan-guages, and Programming (Proc. Conf. 1976), University Press, Edinburgh 1976, 74\u201386"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/S0019-9958(78)90510-7","volume":"37","author":"A Arnold","year":"1978","unstructured":"Arnold, A., Dauchet, M.: For\u00eats alg\u00e9briques et homomorphismes in verses. Information Control 37 (1978), 182\u2013196","journal-title":"Information Control"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Arnold, A., Dauchet, M.: Theorie des magmoides. I. RAIRO Inform. Th\u00e9or. 12 (1978) 235\u2013257; II. ibid. 13 (1979), 135\u2013154","DOI":"10.1051\/ita\/1979130201351"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0304-3975(82)90098-6","volume":"20","author":"A Arnold","year":"1982","unstructured":"Arnold, A., Dauchet, M.: Morphismes et bimorphismes d\u2019arbres. Theoret. Comput. Sci. 20 (1982), 33\u201393","journal-title":"Theoret. Comput. Sci"},{"key":"1_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-79351-6","volume-title":"Reduktionssysteme","author":"J Avenhaus","year":"1995","unstructured":"Avenhaus, J.: Reduktionssysteme. Springer-Verlag, Berlin 1995"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0019-9958(78)90538-7","volume":"37","author":"BS Baker","year":"1978","unstructured":"Baker, B. S.: Tree transducers and tree languages. Information Control 37 (1978), 241\u2013266","journal-title":"Information Control"},{"key":"1_CR16","first-page":"876","volume":"7","author":"BS Baker","year":"1978","unstructured":"Baker, B. S.: Generalized syntax directed translation, tree transducers, and linear space. SIAM J. Comput. 7 (1978), 876\u2013891","journal-title":"SIAM J. Comput"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0019-9958(79)90561-8","volume":"41","author":"B Baker","year":"1979","unstructured":"Baker, B.: Composition of top-down and bottom-up tree transductions. Information Control 41 (1979), 186\u2013213","journal-title":"Information Control"},{"key":"1_CR18","first-page":"409","volume":"5","author":"M Bartha","year":"1982","unstructured":"Bartha, M.: An algebraic definition of attributed tree transformations, Acta Cybern. 5 (1982), 409\u2013421","journal-title":"ActaCybern"},{"key":"1_CR19","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/0022-0000(78)90052-1","volume":"16","author":"J Berger","year":"1978","unstructured":"Berger, J., Pair, C.: Inference for regular bilanguages. J. Comput. Systems Sci. 16 (1978), 100\u2013122","journal-title":"J. Comput. Systems Sci"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0304-3975(82)90019-6","volume":"18","author":"J Berstel","year":"1982","unstructured":"Berstel, J., Reutenauer, J.: Recognizable formal power series on trees. Theoret. Comput. Sci. 18 (1982), 115\u2013148","journal-title":"Theoret. Comput. Sci"},{"key":"1_CR21","first-page":"161","volume-title":"Equality and disequality constraints on direct subterms in tree automata","author":"B Bogaert","year":"1992","unstructured":"Bogaert, B., Tison, S.: Equality and disequality constraints on direct subterms in tree automata. Theoret. Aspects Comput. Sci. (Proc. Symp., 9th STACS 92), Lect. Notes Comput. Sci. 577, Springer-Verlag, Berlin 1992, 161\u2013171"},{"key":"1_CR22","first-page":"43","volume":"22","author":"S Bozapalidis","year":"1988","unstructured":"Bozapalidis, S.: Sur une classe de transformations d\u2019arbres. Inform. Th\u00e9or. Appl. 22 (1988), 43\u201347","journal-title":"Th\u00e9or. Appl"},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF01893886","volume":"28","author":"S Bozapalidis","year":"1991","unstructured":"Bozapalidis, S.: Effective construction of the syntactic algebra of a recognizable series on trees. Acta Inform. 28 (1991), 351\u2013363","journal-title":"Acta Inform"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0304-3975(92)90348-J","volume":"99","author":"S Bozapalidis","year":"1992","unstructured":"Bozapalidis, S.:Alphabetic tree relations. Theoret. Comput. Sci. 99 (1992), 177\u2013211","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR25","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1051\/ita\/1989230404491","volume":"23","author":"S Bozapalidis","year":"1989","unstructured":"Bozapalidis, S., Alexandrakis, A.: Repr\u0107sentations matricelles des s\u0107ries d\u2019arbre reconnaissables. Inform. Th\u00e8or. Applicat. 23 (1989), 449\u2013459","journal-title":"Inform. Th\u00e8or.Applicat"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0304-3975(83)90100-7","volume":"27","author":"S Bozapalidis","year":"1983","unstructured":"Bozapalidis, S., Louscou-Bozapalidou, O.: The rank of formal tree power series. Theoret. Comput. Sci. 27 (1983), 211\u2013215","journal-title":"Theoret. Comput. Sci"},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0019-9958(69)90065-5","volume":"14","author":"WS Brainerd","year":"1969","unstructured":"Brainerd, W. S.: Tree generating regular systems. Information Control 14 (1969), 217\u2013231","journal-title":"Information Control"},{"key":"1_CR28","first-page":"293","volume":"SMC-7","author":"JM Brayer","year":"1977","unstructured":"Brayer, J. M., Fu, K.-S.: A note on the k-tail method of tree grammar inference. IEEE Trans. Systems Man Cybernetics SMC-7 (1977), 293\u2013300","journal-title":"IEEE Trans. Systems Man Cybernetics"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/0020-0190(79)90090-5","volume":"8","author":"A Buda","year":"1979","unstructured":"Buda, A.: Generalized1.5 sequential machines. Inform. Process. Lett. 8 (1979), 38\u201340","journal-title":"Inform. Process.Lett"},{"key":"1_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8130-3","volume-title":"A course in universal algebra","author":"S Burris","year":"1981","unstructured":"Burris, S., Sankappanavar, H. P.: A course in universal algebra. Springer-Verlag, New York 1981"},{"key":"1_CR31","volume-title":"Finite automata and their algebras","author":"JR B\u00fcchi","year":"1989","unstructured":"B\u00fcchi, J. R.: Finite automata and their algebras (ed. D. Siefkes). Springer-Verlag, New York 1989"},{"key":"1_CR32","first-page":"328","volume-title":"Encompassment properties and automata with constraints","author":"A-L Caron","year":"1993","unstructured":"Caron, A.-L., Coquid\u00e9, J.-L., Dauchet, M.: Encompassment properties and automata with constraints. Rewriting Techniques and Applications (Proc. 5th Intern. Conf. 1993), Lect. Notes Comput. Sci. 690, Springer-Verlag, Berlin 1993, 328\u2013342"},{"key":"1_CR33","first-page":"436","volume-title":"Pumping, cleaning and symbolic constraint solving. Automata","author":"A-C Caron","year":"1994","unstructured":"Caron, A.-C., Comon, H., Coquid\u00e9, J.-L., Dauchet, M., Jacquemard, F.: Pumping, cleaning and symbolic constraint solving. Automata, Languages and Programming (Proc. 21st Coll., ICALP\u201994), Lect. Notes Comput. Sci. 820, Springer-Verlag, Berlin 1994, 436\u2013449"},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(94)90101-5","volume":"127","author":"J-L Coquid\u00e9","year":"1994","unstructured":"Coquid\u00e9, J.-L., Dauchet, M., Gilleron, R., V\u00e1gv\u00f6lgyi, S.: Bottom-up tree pushdown automata: classification and connection with rewrite systems. Theoret. Comput. Sci. 127 (1994), 69\u201398","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR35","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0304-3975(82)90003-2","volume":"17","author":"B. Courcelle","year":"1982","unstructured":"Courcelle, B., Franchi-Zannettacci, P.: Attribute grammars and program schemes. I. Theoret. Comput. Sci. 17 (1982), 163\u2013191; II. ibid 235\u2013257","journal-title":"I. Theoret. Comput. Sci."},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: A representation of trees by languages. I. Theoret. Comput. Sci. 6 (1978), 255\u2013279; II. ibid 7 (1978), 25\u201355","DOI":"10.1016\/0304-3975(78)90039-7"},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(86)90050-2","volume":"42","author":"B Courcelle","year":"1986","unstructured":"Courcelle, B.: Equivalence and transformation of regular systems. Theoret. Comput. Sci. 42 (1986), 1\u2013122","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR38","first-page":"93","volume-title":"On recognizable sets and tree automata. Resolution of Equations in Algebraic Structures","author":"B Courcelle","year":"1989","unstructured":"Courcelle, B.: On recognizable sets and tree automata. Resolution of Equations in Algebraic Structures (eds. H. A\u00eft-Kaci and M. Nivat), Academic Press, Boston 1989, 93\u2013126"},{"key":"1_CR39","first-page":"460","volume-title":"Recursive applicative program schemes. Handbook of Theoretical Computer Science. Vol. B. Formal Models and Semantics","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: Recursive applicative program schemes. Handbook of Theoretical Computer Science. Vol. B. Formal Models and Semantics (ed. J. van Leeuwen), Elsevier, Amsterdam 1990, 460\u2013492"},{"key":"1_CR40","first-page":"9297","volume-title":"Transformations de noyaux reconnaissables capacit\u00e9 g\u00e9n\u00e9rative des bimorphismes de for\u00eats","author":"M Dauchet","year":"1979","unstructured":"Dauchet, M., Mongy, J.: Transformations de noyaux reconnaissables capacit\u00e9 g\u00e9n\u00e9rative des bimorphismes de for\u00eats. Fundam. Comput. Theory \u201879 (Proc. Conf. FCT\u201979), Akademie-Verlag, Berlin 1979, 9297"},{"key":"1_CR41","volume-title":"Introduction to lattices and order","author":"BA Davey","year":"1990","unstructured":"Davey, B. A., Priestley, H. A.: Introduction to lattices and order. Cambridge University Press, Cambridge 1990"},{"key":"1_CR42","first-page":"80","volume-title":"Decidability of confluence for ground term rewriting systems","author":"M Dauchet","year":"1985","unstructured":"Dauchet, M., Tison, S.: Decidability of confluence for ground term rewriting systems. Fundam. Comput. Theory (Proc. Conf. FCT\u201985), Lect. Notes Comput. Sci. 199, Springer-Verlag, Berlin 1985, 80\u201389"},{"key":"1_CR43","unstructured":"Dauchet, M., Tison, S.: Structural complexity classes of tree languages. In: [TrAL92], 327\u2013353"},{"key":"1_CR44","first-page":"243","volume-title":"Rewrite systems. Handbook of Theoretical Computer Science. Vol. B. Formal Models and Semantics","author":"N Dershowitz","year":"1990","unstructured":"Dershowitz, N, Jouannaud, J.-P.: Rewrite systems. Handbook of Theoretical Computer Science. Vol. B. Formal Models and Semantics (ed. J. van Leeuwen), Elsevier, Amsterdam 1990, 243\u2013320"},{"key":"1_CR45","first-page":"187","volume":"88","author":"M Dauchet","year":"1990","unstructured":"Dauchet, M., Heuillard, T., Lescanne, P., Tison, S.: Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems. Information Control 88 (1990), 187\u2013201","journal-title":"Information Control"},{"key":"1_CR46","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"JE Doner","year":"1970","unstructured":"Doner, J. E.: Tree acceptors and some of their applications. J. Comput. Syst. Sci. 4 (1970), 406\u2013451","journal-title":"J. Comput. Syst. Sci"},{"key":"1_CR47","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1016\/S0019-9958(67)90670-5","volume":"11","author":"S Eilenberg","year":"1967","unstructured":"Eilenberg, S., Wright, J. B.: Automata in general algebras. Information Control 11 (1967), 452\u2013470","journal-title":"Information Control"},{"key":"1_CR48","volume-title":"Tree automata and tree grammars. Lecture notes","author":"J Engelfriet","year":"1975","unstructured":"Engelfriet, J.: Tree automata and tree grammars. Lecture notes, DAIMI FN-10, Inst. Mathem., Aarhus University, Aarhus 1975"},{"key":"1_CR49","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/BF01704020","volume":"9","author":"J Engelfriet","year":"1975","unstructured":"Engelfriet, J.: Bottom-up and top-down tree transformations. A com- parison. Math. Systems Theory 9 (1975), 198\u2013231","journal-title":"A com- parison. Math. Systems Theory"},{"key":"1_CR50","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF01683280","volume":"10","author":"J. Engelfriet","year":"1976","unstructured":"Engelfriet, J.: Top-down tree transducers with regular look-ahead. Math. Systems Theory 10 (1976\/1977), 289\u2013303","journal-title":"Math. Systems Theory"},{"key":"1_CR51","first-page":"103","volume-title":"A hierarchy of tree transducers. Les Arbres en Alg\u00e8breet en Programmation","author":"J Engelfriet","year":"1978","unstructured":"Engelfriet, J.: A hierarchy of tree transducers. Les Arbres en Alg\u00e8breet en Programmation (Proc. 3rd Coll., Lille 1979), University of Lille, Lille 1978, 103\u2013106"},{"key":"1_CR52","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/B978-0-12-115350-2.50014-2","volume-title":"Formal Language Theory","author":"J Engelfriet","year":"1980","unstructured":"Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages. Formal Language Theory (ed. R. V. Book), Academic Press, New York 1980, 241\u2013286"},{"key":"1_CR53","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01786975","volume":"15","author":"J Engelfriet","year":"1982","unstructured":"Engelfriet, J.: Three hierarchies of transducers. Math. Systems Theory 15 (1982), 95\u2013125","journal-title":"Math. Systems Theory"},{"key":"1_CR54","doi-asserted-by":"crossref","unstructured":"Engelfriet, J., Schmidt, E. M.: IO and OI. I. J. Comput. Systems Sci. 15 (1977), 328\u2013353; II. ibid 16 (1978), 67\u201399","DOI":"10.1016\/0022-0000(78)90051-X"},{"key":"1_CR55","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0022-0000(85)90066-2","volume":"31","author":"J Engelfriet","year":"1985","unstructured":"Engelfriet, J., Vogler, H.: Macro tree transducers. J. Comput. Systems Sci. 31 (1985), 71\u2013145","journal-title":"J. Comput. Systems Sci"},{"key":"1_CR56","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0304-3975(86)90052-6","volume":"42","author":"J Engelfriet","year":"1986","unstructured":"Engelfriet, J., Vogler, H.: Pushdown machines for macro tree transducers. Theoret. Comput. Sci. 42 (1986), 251\u2013369","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR57","first-page":"245","volume":"73","author":"J Engelfriet","year":"1987","unstructured":"Engelfriet, J., Vogler, H.: Look-ahead on pushdowns. Information Control 73 (1987), 245\u2013279","journal-title":"Information Control"},{"key":"1_CR58","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF02915449","volume":"26","author":"J Engelfriet","year":"1988","unstructured":"Engelfriet, J., Vogler, H.: High level tree transducers and iterated pushdown tree transducers. Acta Inform. 26 (1988), 131\u2013192","journal-title":"Acta Inform"},{"key":"1_CR59","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(91)90353-4","volume":"78","author":"J Engelfriet","year":"1991","unstructured":"Engelfriet, J., Vogler, H.: Modular tree transducers. Theoret. Comput. Sci. 78 (1991), 267\u2013303","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR60","first-page":"1","volume":"6","author":"Z. \u00c9sik","year":"1980","unstructured":"\u00c9sik, Z.: Decidability results concerning tree transducers. I. Acta Cybern. 5 (1980), 1\u201320; II. ibid\n                     6 (1983), 303\u2013314","journal-title":"II. ibid"},{"key":"1_CR61","doi-asserted-by":"crossref","first-page":"205","DOI":"10.3233\/FI-1986-9204","volume":"IX","author":"Z \u00c9sik","year":"1986","unstructured":"\u00c9sik, Z., G\u0107cseg, F.: Type independent varieties and metric equivalence of tree automata. Fundam. Inform. IX (1986), 205\u2013216","journal-title":"Fundam. Inform"},{"key":"1_CR62","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(87)90066-1","volume":"53","author":"Z \u00c9sik","year":"1987","unstructured":"\u00c9sik, Z., G\u0107cseg, F.: On a representation of tree automata. Theoret. Comput. Sci. 53 (1987), 243\u2013255","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR63","doi-asserted-by":"crossref","unstructured":"Fischer, M. J.: Grammars with macro-like productions. 9th Ann. IEEE Symp. on Switching and Automata Theory (Proc. Symp. 1968), 131\u2013142","DOI":"10.1109\/SWAT.1968.12"},{"key":"1_CR64","volume-title":"Syntactic pattern recognition and applications. Prentice-Hall","author":"K-S Fu","year":"1982","unstructured":"Fu, K.-S.: Syntactic pattern recognition and applications. Prentice-Hall, Englewood Cliffs, N. J. 1982"},{"key":"1_CR65","first-page":"1087","volume":"-22","author":"F.-S. Fu","year":"1973","unstructured":"Fu, F.-S., Brayer, J. M.: Tree systems for syntactic pattern recognition. IEEE Trans. Computers C-22 (1973), 1087\u20131099","journal-title":"IEEE Trans. Computers C"},{"key":"1_CR66","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF00979871","volume":"13","author":"H Fukuda","year":"1984","unstructured":"Fukuda, H., Kamata, K.: Inference of tree automata from sample set of trees. Intern. J. Comput. Inform. Sci. 13 (1984), 177\u2013196","journal-title":"Intern. J. Comput. Inform. Sci."},{"key":"1_CR67","first-page":"261","volume":"5","author":"Z F\u00fcl\u00f6p","year":"1981","unstructured":"F\u00fcl\u00f6p, Z.: On attributed tree transducers. Acta Cybern. 5 (1981), 261\u2013279","journal-title":"Acta Cybern"},{"key":"1_CR68","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0304-3975(91)90376-D","volume":"88","author":"Z F\u00fcl\u00f6p","year":"1991","unstructured":"F\u00fcl\u00f6p, Z.: A complete description for a monoid of deterministic bottom-up tree transformation classes. Theoret. Comput. Sci. 88 (1991), 253\u2013268","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR69","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(94)90241-0","volume":"134","author":"Z F\u00fcl\u00f6p","year":"1994","unstructured":"F\u00fcl\u00f6p, Z.: Undecidable properties of deterministic top-down tree transducers, Theoret. Comput. Sci. 134 (1994), 311\u2013328","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR70","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0304-3975(93)90191-U","volume":"108","author":"Z F\u00fcl\u00f6p","year":"1993","unstructured":"F\u00fcl\u00f6p, Z., Herrmann, F., V\u00e1gv\u00f6lgyi, S., Vogler, H.: Tree transducers with external functions. Theoret. Comput. Sci. 108 (1993), 185\u2013236","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR71","first-page":"49","volume":"8","author":"Z F\u00fcl\u00f6p","year":"1987","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: Results on compositions of deterministic root- to-frontier tree transformations. Acta Cybern. 8 (1987), 49\u201361","journal-title":"Acta Cybern"},{"key":"1_CR72","first-page":"259","volume":"8","author":"Z F\u00fcl\u00f6p","year":"1987","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.:On ranges of compositions of deterministic root-to-frontier tree transformations. Acta Cybern. 8 (1987), 259\u2013266","journal-title":"Acta Cybern"},{"key":"1_CR73","first-page":"175","volume-title":"Iterated deterministic top-down look-ahead. Fundam. Comput","author":"Z F\u00fcl\u00f6p","year":"1989","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: Iterated deterministic top-down look-ahead. Fundam. Comput. Theory (Proc. FCT\u201989), Lect. Notes Comput. Sci. 380, Springer-Verlag, Berlin 1989, 175\u2013184"},{"key":"1_CR74","first-page":"175","volume":"39","author":"Z F\u00fcl\u00f6p","year":"1989","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: Congruential tree languages are the same as recognizable tree languages. Bull. EATCS 39 (1989), 175\u2013185","journal-title":"Bull. EATCS"},{"key":"1_CR75","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF02088010","volume":"21","author":"Z F\u00fcl\u00f6p","year":"1989","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: Variants of top-down tree transducers with look-ahead. Math. Systems Theory 21 (1989), 125\u2013145","journal-title":"Math. Systems Theory"},{"key":"1_CR76","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0020-0190(89)90178-6","volume":"33","author":"Z F\u00fcl\u00f6p","year":"1989","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: Top-down tree transducers with deterministic top-down look-ahead. Inform. Process. Lett. 33 (1989\/90), 3\u20135","journal-title":"Inform. Process. Lett."},{"key":"1_CR77","doi-asserted-by":"crossref","first-page":"211","DOI":"10.3233\/FI-1990-13205","volume":"XIII","author":"Z F\u00fcl\u00f6p","year":"1990","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: A characterization of irreducible sets modulo left-linear term rewriting systems by tree automata. Fundam. Inform. XIII (1990), 211\u2013226","journal-title":"Fundam. Inform"},{"key":"1_CR78","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(91)90312-P","volume":"81","author":"Z F\u00fcl\u00f6p","year":"1991","unstructured":"F\u00fcl\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: A complete classification of deterministic root-to-frontier tree transformation classes. Theor. Comput. Sci. 81 (1991), 1\u201315","journal-title":"Theor. Comput. Sci."},{"key":"1_CR79","unstructured":"Fiil\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: Decidability of the inclusion in monoids generated by tree transformation classes. In: [TrAL92], 381\u2013408"},{"key":"1_CR80","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1006\/inco.1995.1016","volume":"116","author":"Z Fiil\u00f6p","year":"1995","unstructured":"Fiil\u00f6p, Z., V\u00e1gv\u00f6lgyi, S.: Attributed tree transducers cannot induce all deterministic bottom-up tree transformations. Information Computation 116 (1995), 231\u2013240","journal-title":"Information Computation"},{"key":"1_CR81","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0304-3975(85)90089-1","volume":"37","author":"JH Gallier","year":"1985","unstructured":"Gallier, J. H., Book, R. V.: Reductions in tree replacement systems. Theor. Comput. Sci. 37 (1985), 123\u2013150","journal-title":"Theor. Comput. Sci."},{"key":"1_CR82","first-page":"163","volume":"48","author":"F G\u00e9cseg","year":"1985","unstructured":"G\u00e9cseg, F.: Metric equivalence of tree automata. Acta Sci. Math. 48 (1985), 163\u2013171","journal-title":"Acta Sci. Math."},{"key":"1_CR83","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/3-540-58131-6_42","volume-title":"Homomorphic representations by products of tree au-tomata. Results and Trends in Theoretical Computer Science","author":"F G\u00e9cseg","year":"1994","unstructured":"G\u00e9cseg, F.: Homomorphic representations by products of tree au-tomata. Results and Trends in Theoretical Computer Science (Proc. Coll. 1994), Lect. Notes Comput. Sci. 812, Springer-Verlag, Berlin 1994,131\u2013139"},{"key":"1_CR84","first-page":"497","volume":"57","author":"F G\u00e9cseg","year":"1993","unstructured":"G\u00e9cseg, F., Imreh, B.: On finite isomorphically complete systems of tree automata. Acta Sci. Math. 57 (1993), 497\u2013502","journal-title":"Acta Sci. Math."},{"key":"1_CR85","volume-title":"Tree automata","author":"F G\u00e9cseg","year":"1984","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree automata. Akad\u00e9miai Kiad\u00f3, Budapest 1984"},{"key":"1_CR86","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF00975630","volume":"5","author":"RC Gonzalez","year":"1976","unstructured":"Gonzalez, R. C., Edwards, J. J., Thomason, M. G.: An algorithm for the inference of tree grammars. Intern. J. Comput. Information Sci. 5 (1976), 145\u2013164","journal-title":"Intern. J. Comput. Information Sci"},{"key":"1_CR87","first-page":"148","volume-title":"Decision problems for term rewriting systems and recognizable tree languages","author":"R Gilleron","year":"1991","unstructured":"Gilleron, R.: Decision problems for term rewriting systems and recognizable tree languages. Theoret. Aspects Comput. Sci. (Proc. STACS\u201991), Lect. Notes Comput. Sci. 480, Springer-Verlag, Berlin 1991, 148\u2013159"},{"key":"1_CR88","volume-title":"Syntactic pattern recognition: an introduction. Addison-Wesley","author":"RC Gonzalez","year":"1978","unstructured":"Gonzalez, R. C., Thomason, M. G.: Syntactic pattern recognition: an introduction. Addison-Wesley, Reading, MA 1978"},{"key":"1_CR89","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01744582","volume":"16","author":"I Guessarian","year":"1983","unstructured":"Guessarian, I.: Pushdown tree automata. Math. Systems Theory 16 (1983), 237\u2013263","journal-title":"Math. Systems Theory"},{"key":"1_CR90","unstructured":"Guessarian, I.: Trees and algebraic semantics. In: [TrAL92], 291\u2013310"},{"key":"1_CR91","first-page":"137","volume":"35","author":"U Heuter","year":"1988","unstructured":"Heuter, U.: Definite tree languages. Bull. EATCS 35 (1988), 137\u2013144","journal-title":"Bull. EATCS"},{"key":"1_CR92","volume-title":"Zur Klassifizierung regul\u00e4rer Baumsprachen. Disseration","author":"U Heuter","year":"1989","unstructured":"Heuter, U.: Zur Klassifizierung regul\u00e4rer Baumsprachen. Disseration, RWTH, Technical University of Aachen, Faculty of Science, 1989"},{"key":"1_CR93","first-page":"270","volume-title":"Generalized definite tree languages. Mathem. Found. Comput","author":"U Heuter","year":"1989","unstructured":"Heuter, U.: Generalized definite tree languages. Mathem. Found. Comput. Sci. (Proc. Symp. MFCS\u201989), Lect. Notes in Comput. Sci. 379, Springer-Verlag, Berlin 1989, 270\u2013280"},{"key":"1_CR94","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1051\/ita\/1991250201251","volume":"25","author":"U Heuter","year":"1991","unstructured":"Heuter, U.: First-order properies of trees, star-free, and periodicity. Inform. Th\u0107or. Applic. 25 (1991), 125\u2013145","journal-title":"Inform. Th\u0107or. Applic."},{"key":"1_CR95","first-page":"147","volume":"6","author":"G Horvath","year":"1981","unstructured":"Horvath, Gy.: Functor state machines. Acta Cybernet. 6 (1981), 147\u2013172","journal-title":"Acta Cybernet"},{"key":"1_CR96","first-page":"349","volume-title":"Equations and rewrite rules: a survey. Formal Language Theory: Perspectives and Open Problems","author":"G Huet","year":"1980","unstructured":"Huet, G., Oppen, D. C.: Equations and rewrite rules: a survey. Formal Language Theory: Perspectives and Open Problems (ed. R. Book), Academic Press, New York 1980, 349\u2013405"},{"key":"1_CR97","first-page":"237","volume":"10","author":"B Imreh","year":"1992","unstructured":"Imreh, B.: On a special composition of tree automata. Acta Cybern. 10 (1992), 237\u2013242","journal-title":"Acta Cybern"},{"key":"1_CR98","first-page":"11","volume":"12","author":"B Imreh","year":"1995","unstructured":"Imreh, B.: On isomorphic representation of nondeterministic tree au-tomata. Acta Cybern. 12 (1995), 11\u201322","journal-title":"Acta Cybern"},{"key":"1_CR99","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/S0022-0000(75)80019-5","volume":"10","author":"AK Joshi","year":"1975","unstructured":"Joshi, A. K., Levy, L. S., Takahashi, M.: Tree adjunct grammars. J. Comput. Systems Sci. 10 (1975), 136\u2013163","journal-title":"J. Comput. Systems Sci"},{"key":"1_CR100","unstructured":"Joshi, A. K., Schabes, Y.: Tree-adjoining grammars and lexicalized grammars. In: [TrAL92], 409\u2013431"},{"key":"1_CR101","first-page":"255","volume":"10","author":"E Jurvanen","year":"1992","unstructured":"Jurvanen, E.: The Boolean closure of DR-recognizable tree languages. Acta Cybern. 10 (1992), 255\u2013272","journal-title":"Acta Cybern"},{"key":"1_CR102","volume-title":"On recognizing trees deterministically from root to fron-tier. Doctoral Thesis","author":"E Jurvanen","year":"1995","unstructured":"Jurvanen, E.: On recognizing trees deterministically from root to fron-tier. Doctoral Thesis, University of Turku, Turku 1995"},{"key":"1_CR103","first-page":"3","volume-title":"Developments in Language Theory","author":"E Jurvanen","year":"1994","unstructured":"Jurvanen, E., Potthoff, A., Thomas, W.: Tree languages recognizable by regular frontier check. Developments in Language Theory (eds. G. Rozenberg and A. Salomaa, Proc. Conf. Turku, Finland 1993). World Scientific, Singapore 1994, 3\u201317"},{"key":"1_CR104","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(83)80021-7","volume":"57","author":"T Kamimura","year":"1983","unstructured":"Kamimura, T.: Tree automata and attribute grammars. Information Control 57 (1983), 1\u201320","journal-title":"Information Control"},{"key":"1_CR105","doi-asserted-by":"crossref","unstructured":"Kamata, K.: Inference methods for tree automata from sample set of trees. Systems, Man and Cybernetics (Proc. 1988 IEEE Intern. Conf.), 490\u2013493","DOI":"10.1109\/ICSMC.1988.754345"},{"key":"1_CR106","volume-title":"On the inductive inference of regular string and tree languages. Dissertation, University of Turku","author":"T Knuutila","year":"1994","unstructured":"Knuutila, T.: On the inductive inference of regular string and tree languages. Dissertation, University of Turku, Dept. of Computer Science, Turku 1994"},{"key":"1_CR107","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(94)90033-7","volume":"129","author":"T Knuutila","year":"1994","unstructured":"Knuutila, T., Steinby, M.: The inference of tree languages from finite samples: an algebraic approach. Theoret. Comput. Sci. 129 (1994), 337\u2013367","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR108","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Complexity of finitely presented algebras. 9th Ann. ACM Symp. on Theory of Computing (Proc. Symp., 1977), 164\u2013177","DOI":"10.1145\/800105.803406"},{"key":"1_CR109","first-page":"299","volume-title":"On relationship between term rewriting systems and regular tree languages. Rewriting Techniques and Applications","author":"G Kucherov","year":"1991","unstructured":"Kucherov, G.: On relationship between term rewriting systems and regular tree languages. Rewriting Techniques and Applications (Proc. 4th Intern. Conf.), Lect. Notes Comput. Sci. 488, Springer-Verlag, Berlin 1991, 299\u2013311"},{"key":"1_CR110","first-page":"261","volume":"11","author":"K\u00fchnemann, A., Vogler, H.","year":"1994","unstructured":"K\u00fchnemann, A., Vogler, H.: A pumping lemma for output languages of attributed tree transducers. Acta Cybern. 11 (1994), 261\u2013305","journal-title":"Acta Cybern"},{"key":"1_CR111","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/S0019-9958(73)90732-8","volume":"23","author":"LS Levy","year":"1973","unstructured":"Levy, L. S.: Structural aspects of local adjunct grammars. Information Control 23 (1973), 260\u2013287","journal-title":"Information Control"},{"key":"1_CR112","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1109\/TPAMI.1981.4767101","volume":"-3","author":"B. Levine","year":"1981","unstructured":"Levine, B.: Derivatives of tree sets with applications to grammatical inference. IEEE Trans. Pattern Anal. Machine Intelligence PAMI-3 (1981), 285\u2013293","journal-title":"IEEE Trans. Pattern Anal. Machine Intelligence"},{"key":"1_CR113","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/S0019-9958(78)90849-5","volume":"39","author":"LS Levy","year":"1978","unstructured":"Levy, L. S., Joshi, A. K.: Skeletal structural descriptions. Information Control 39 (1978), 192\u2013211","journal-title":"Information Control"},{"key":"1_CR114","unstructured":"Magidor, M., Moran, G.: Finite automata over finite trees. Technical Report 30, Hebrew University, Jerusalem 1969"},{"key":"1_CR115","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0019-9958(67)90353-1","volume":"11","author":"J Mezei","year":"1967","unstructured":"Mezei, J., Wright, J. B.: Algebraic automata and context-free sets. Information Control 11 (1967), 3\u201329","journal-title":"Information Control"},{"key":"1_CR116","volume-title":"Structural methods in pattern recognitionLondon","author":"L Miclet","year":"1986","unstructured":"Miclet, L.: Structural methods in pattern recognition. North-Oxford, London 1986"},{"key":"1_CR117","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0020-0190(94)00022-0","volume":"50","author":"E Moriya","year":"1994","unstructured":"Moriya, E.: On two-way tree automata. Inform. Process. Lett. 50 (1994), 117\u2013121","journal-title":"Inform. Process. Lett."},{"key":"1_CR118","first-page":"63","volume":"8","author":"I Neum\u00fcller","year":"1987","unstructured":"Neum\u00fcller, I.: The invertability of tree transducers. Acta Cybern. 8 (1987), 63\u201378","journal-title":"Acta Cybern"},{"key":"1_CR119","first-page":"255","volume":"15","author":"M Nivat","year":"1975","unstructured":"Nivat, M.: On the interpretation of recursive polyadic program schemes. Symp. Mathematica 15 (1975), 255\u2013281","journal-title":"Symp. Mathematica"},{"key":"1_CR120","unstructured":"Nivat, M.: Binary tree codes. In: [TrAL92], 1\u201320"},{"key":"1_CR121","first-page":"186","volume":"38","author":"M Nivat","year":"1989","unstructured":"Nivat, M., Podelski, A.: Definite tree automata (cont\u2019d). Bull. EATCS 38 (1989), 186\u2013190","journal-title":"Bull. EATCS"},{"key":"1_CR122","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0012-365X(93)90379-8","volume":"114","author":"M Nivat","year":"1993","unstructured":"Nivat, M., Podelski, A.: Another variation on the common subexpression problem. Discr. Math. 114 (1993), 379\u2013401","journal-title":"Discr. Math."},{"key":"1_CR123","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(87)90100-9","volume":"49","author":"M Oyamaguchi","year":"1987","unstructured":"Oyamaguchi, M.: The Church\u00a1\u00aaRosser property for ground term-rewriting systems is decidable. Theoret. Comput. Sci. 49 (1987), 43\u201379","journal-title":"Theoret. Comput. Sci"},{"key":"1_CR124","first-page":"1530","volume-title":"Inference for regular bilanguages","author":"C Pair","year":"1976","unstructured":"Pair, C.: Inference for regular bilanguages. Formal Languages and Programming (Proc. Semin. 1975), North-Holland, Amsterdam 1976, 1530"},{"key":"1_CR125","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/S0019-9958(68)90999-6","volume":"13","author":"C Pair","year":"1968","unstructured":"Pair, C., Quere, A.: D\u00e9finition et etude des bilangages r\u00e9guliers. Information Control 13 (1968), 565\u2013593","journal-title":"Information Control"},{"key":"1_CR126","first-page":"150","volume-title":"On reverse and general definite tree languages. Automata, Languages and Programming","author":"P P\u00e9ladeau","year":"1992","unstructured":"P\u00e9ladeau, P., Podelski, A.: On reverse and general definite tree languages. Automata, Languages and Programming (Proc. 19th ICALP), Lect. Notes in Comput. Sci. 623, Springer-Verlag, Berlin 1992, 150\u2013161"},{"key":"1_CR127","unstructured":"Podelski, A.: A monoid approach to tree automata. In: [TrAL92], 41\u201356"},{"key":"1_CR128","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0304-3975(94)90270-4","volume":"126","author":"A Potthoff","year":"1994","unstructured":"Potthoff, A.: Modulo counting quantifiers over finite trees. Theoret. Comput. Sci. 126 (1994), 97\u2013112","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR129","volume-title":"Logische Klassifizierung regul\u00e4rer Baumsprachen","author":"A Potthoff","year":"1994","unstructured":"Potthoff, A.: Logische Klassifizierung regul\u00e4rer Baumsprachen. Bericht Nr. 9410, Inst. Informatik u. Prakt. Math., Chr.-Albrechts University, Kiel, Kiel 1994"},{"key":"1_CR130","first-page":"396","volume-title":"Regular tree languages without unary symbols are star-free. Fundam. Comput","author":"A Potthoff","year":"1993","unstructured":"Potthoff, A., Thomas, W.: Regular tree languages without unary symbols are star-free. Fundam. Comput. Theory (Proc. Conf. FCT\u201993), Lect. Notes in Comput. Sci. 710, Springer-Verlag, Berlin 1993,396\u2013405"},{"key":"1_CR131","unstructured":"Raoult, J.-C.: A survey of tree transductions. In: [TrAL92], 311\u2013325"},{"key":"1_CR132","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1145\/321738.321750","volume":"20","author":"BK Rosen","year":"1973","unstructured":"Rosen, B. K.: Tree-manipulating systems and Church-Rosser theorems. J. ACM 20 (1973), 160\u2013187","journal-title":"J. ACM"},{"key":"1_CR133","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0022-4049(92)90085-T","volume":"77","author":"KI Rosenthal","year":"1992","unstructured":"Rosenthal, K. I.: Quantaloid nuclei, the syntactic congruence and tree automata. J. Pure Appl. Algebra 77 (1992), 189\u2013205","journal-title":"J. Pure Appl. Algebra"},{"key":"1_CR134","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1017\/S0960129500000487","volume":"4","author":"KI Rosenthal","year":"1994","unstructured":"Rosenthal, K. I.: A categorical look at tree automata and context-free languages. Math. Struct. in Comp. Science 4 (1994), 287\u2013293","journal-title":"Math. Struct. in Comp. Science"},{"key":"1_CR135","first-page":"143","volume-title":"Context-free grammars on trees. 1st Ann. ACM Symp. Theory Comput","author":"WC Rounds","year":"1969","unstructured":"Rounds, W. C.: Context-free grammars on trees. 1st Ann. ACM Symp. Theory Comput. (Proc. Symp. 1969), 143\u2013148"},{"key":"1_CR136","first-page":"109","volume-title":"Tree-oriented proofs of some theorems on context-free and indexed languages. 2nd Ann. ACM Symp. Theory Comput","author":"WC Rounds","year":"1970","unstructured":"Rounds, W. C.: Tree-oriented proofs of some theorems on context-free and indexed languages. 2nd Ann. ACM Symp. Theory Comput. (Proc. Symp. 1970), 109\u2013116"},{"key":"1_CR137","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF01695769","volume":"4","author":"WC Rounds","year":"1970","unstructured":"Rounds, W. C.: Mappings and grammars on trees. Math. Systems Theory 4 (1970), 257\u2013287","journal-title":"Math. Systems Theory"},{"key":"1_CR138","volume-title":"Syntactic monoids of forests (in Finnish). Master\u2019s Thesis, University of Turku","author":"K Salomaa","year":"1983","unstructured":"Salomaa, K.: Syntactic monoids of forests (in Finnish). Master\u2019s Thesis, University of Turku, Dept. of Mathematics, Turku 1983"},{"key":"1_CR139","first-page":"158","volume-title":"Alternating bottom-up tree automata. Trees in Algebra and Programming","author":"K Salomaa","year":"1986","unstructured":"Salomaa, K.: Alternating bottom-up tree automata. Trees in Algebra and Programming (Proc. 11th CAAP), Lect. Notes Comput. Sci. 214, Springer-Verlag, Berlin 1986, 158\u2013171"},{"key":"1_CR140","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1051\/ita\/1988220303191","volume":"22","author":"K Salomaa","year":"1988","unstructured":"Salomaa, K.: Yield-languages recognized by alternating tree recognizers. RAIRO Inform. Th\u0107or. 22 (1988), 319\u2013339","journal-title":"RAIRO Inform. Th\u0107or"},{"key":"1_CR141","series-title":"Acta Univ. Turkuensis, Ser.","first-page":"A 192","volume-title":"Alternating tree pushdown automata","author":"K Salomaa","year":"1988","unstructured":"Salomaa, K.: Alternating tree pushdown automata. Acta Univ. Turkuensis, Ser. A 192, Turku 1988"},{"key":"1_CR142","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0022-0000(88)90014-1","volume":"37","author":"K Salomaa","year":"1988","unstructured":"Salomaa, K.: Deterministic tree pushdown automata and tree rewriting systems. J. Comput. System Sci. 37 (1988), 367\u2013394","journal-title":"J. Comput. System Sci"},{"key":"1_CR143","first-page":"372","volume-title":"Representation of recursively enumerable languages using alternating finite tree recognizers. Fundam. Comput","author":"K Salomaa","year":"1989","unstructured":"Salomaa, K.: Representation of recursively enumerable languages using alternating finite tree recognizers. Fundam. Comput. Theory (Proc. FCT\u201989), Lect. Notes Comput. Sci. 380, Springer-Verlag, Berlin 1989, 372\u2013383"},{"key":"1_CR144","first-page":"173","volume":"10","author":"K Salomaa","year":"1992","unstructured":"Salomaa, K.: Alternation bounds for tree automata. Acta Cybern. 10 (1992), 173\u2013197","journal-title":"Acta Cybern"},{"key":"1_CR145","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0304-3975(94)90099-X","volume":"127","author":"K Salomaa","year":"1994","unstructured":"Salomaa, K.: Synchronized tree automata. Theoret. Comput. Sci. 127 (1994), 25\u201351","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR146","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0022-0000(85)90002-9","volume":"30","author":"KM Schimpf","year":"1985","unstructured":"Schimpf, K. M., Gallier, J. H.: Tree pushdown automata. J. Comput. System Sci. 30 (1985), 25\u201340","journal-title":"J. Comput. System Sci."},{"key":"1_CR147","doi-asserted-by":"crossref","unstructured":"Seidl, H.: Deciding equivalence of finite tree automata.. Theor. Aspects Comput. Sci. (Proc. STACS\u201988), Lect. Notes Comput. Sci. 349, Springer-Verlag, Berlin 1989, 480\u2013492","DOI":"10.1007\/BFb0029009"},{"key":"1_CR148","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/BF00263578","volume":"26","author":"H Seidl","year":"1989","unstructured":"Seidl, H.: On the finite degree of ambiguity of finite tree automata. Acta Inform. 26 (1989), 527\u2013542","journal-title":"Acta Inform"},{"key":"1_CR149","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0304-3975(92)90281-J","volume":"106","author":"H Seidl","year":"1992","unstructured":"Seidl, H.: Single-valuedness of tree transducers is decidable in polynomial time. Theoret. Comput. Sci. 106 (1992), 135\u2013181","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR150","unstructured":"Seidl, H.: Ambiguity and valuedness. In: [TrAL92], 355\u2013380"},{"key":"1_CR151","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF01192143","volume":"27","author":"H Seidl","year":"1994","unstructured":"Seidl, H.: Equivalence of finite-valued tree transducers is decidable. Math. Systems Theory 27 (1994), 285\u2013346","journal-title":"Math. Systems Theory"},{"key":"1_CR152","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(85)90077-5","volume":"41","author":"G Slutzki","year":"1985","unstructured":"Slutzki, G.: Alternating tree automata. Theoret. Comput. Sci. 41 (1985), 305\u2013318","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR153","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0304-3975(94)00111-U","volume":"143","author":"G Slutzki","year":"1995","unstructured":"Slutzki, G., V\u00e1gv\u00f6lgyi, S.: Deterministic top-down tree transducers with iterated look-ahead. Theoret. Comput. Sci. 143 (1995), 285\u2013308","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR154","first-page":"226","volume-title":"Syntactic algebras and varieties of recognizable sets. Les Arbres en Alg\u00e8bre et en Programmation","author":"M Steinby","year":"1979","unstructured":"Steinby, M.: Syntactic algebras and varieties of recognizable sets. Les Arbres en Alg\u00e8bre et en Programmation (Proc. 4th Coll., Lille 1979), University of Lille, Lille 1979, 226\u2013240"},{"key":"1_CR155","first-page":"745","volume-title":"On certain algebraically defined tree transformations","author":"M Steinby","year":"1986","unstructured":"Steinby, M.: On certain algebraically defined tree transformations. Al-gebra, Combinatorics and Logic in Computer Science (Proc. Conf. 1983), North-Holland, Amsterdam 1986, 745\u2013764"},{"key":"1_CR156","first-page":"444","volume-title":"Tree language problems in pattern recognition theory. Fundam. Comput","author":"M Steinby","year":"1989","unstructured":"Steinby, M.: Tree language problems in pattern recognition theory. Fundam. Comput. Theory (Proc. FCT\u201989), Lect. Notes Comput. Sci. 380, Springer-Verlag, Berlin 1989, 444\u2013450"},{"issue":"1","key":"1_CR157","first-page":"19","volume":"26","author":"M. Steinby","year":"1990","unstructured":"Steinby, M.: A formal theory of errors in tree representations of pat-terns. J. Inform. Process. Cybern. EIK 26 (1990) 1\/2, 19\u201332","journal-title":"J. Inform. Process. Cybern. EIK"},{"key":"1_CR158","unstructured":"Steinby, M.: A theory of tree language varieties. In: [TrAL92], 57\u201381"},{"key":"1_CR159","volume-title":"General varieties of tree languages","author":"M Steinby","year":"1995","unstructured":"Steinby, M.: General varieties of tree languages. Technical Report LITP 95\/30, Institute Blaise Pascal, Universite Denis Piderot, Paris 1995"},{"key":"1_CR160","first-page":"475","volume-title":"Primitive transformations of regular sets and recognizable sets. Automata, Languages and Programming","author":"M Takahashi","year":"1973","unstructured":"Takahashi, M.: Primitive transformations of regular sets and recognizable sets. Automata, Languages and Programming (Proc. Coll. 1972), North-Holland, Amsterdam 1973, 475\u2013480"},{"key":"1_CR161","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(75)90058-3","volume":"27","author":"M Takahashi","year":"1975","unstructured":"Takahashi, M.: Generalizations of regular sets and their application to a study of context-free languages. Information Control 27 (1975), 1\u201336","journal-title":"Information Control"},{"key":"1_CR162","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1007\/3-540-08342-1_41","volume-title":"Rational relations on binary trees. Automata, Languages and Programming","author":"M Takahashi","year":"1977","unstructured":"Takahashi, M.: Rational relations on binary trees. Automata, Languages and Programming (Proc. 4th Coll. 1977), Lect. Notes Comput. Sci. 52, Springer-Verlag, Berlin 1977, 524\u2013538"},{"key":"1_CR163","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0022-0000(67)80022-9","volume":"1","author":"JW Thatcher","year":"1967","unstructured":"Thatcher, J. W.: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. J. Comput. Systems Sci. 1 (1967), 317\u2013322","journal-title":"J. Comput. Systems Sci"},{"key":"1_CR164","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/S0022-0000(70)80017-4","volume":"4","author":"JW Thatcher","year":"1970","unstructured":"Thatcher, J. W.: Generalized2 sequential machines. J. Comput. System Sci. 4 (1970), 339\u2013367","journal-title":"J. Comput. System Sci"},{"key":"1_CR165","first-page":"143","volume-title":"Currents in the Theory of Computing","author":"JW Thatcher","year":"1973","unstructured":"Thatcher, J. W.: Tree automata: an informal survey. Currents in the Theory of Computing (ed. A. V. Aho), Prentice-Hall, Englewood Cliffs, N.J. (1973), 143\u2013172"},{"key":"1_CR166","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"JW Thatcher","year":"1968","unstructured":"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 (1968), 57\u201381","journal-title":"Math. Systems Theory"},{"key":"1_CR167","first-page":"270","volume-title":"Logical aspects in the study of tree languages","author":"W Thomas","year":"1984","unstructured":"Thomas, W.: Logical aspects in the study of tree languages. Trees in Algebra and Programming (Proc. 9th CAAP), Cambridge University Press, Cambridge 1984, 270\u2013280"},{"key":"1_CR168","first-page":"133","volume-title":"Vol. B. Formal Models and Semantics","author":"W Thomas","year":"1990","unstructured":"Thomas, W.: Automata on infinite objects. Handbook of Theoretical Computer Science. Vol. B. Formal Models and Semantics (ed. J. van Leeuwen), Elsevier, Amsterdam 1990, 133\u2013191"},{"key":"1_CR169","volume-title":"Tree Automata and Languages","year":"1992","unstructured":"Tree Automata and Languages (eds. M. Nivat, A. Podelski). North-Holland, Amsterdam 1992"},{"key":"1_CR170","first-page":"91","volume":"26","author":"I Tsomokos","year":"1989","unstructured":"Tsomokos, I.: K-treeautomata and their relation to weighted context-free grammars Intern. J. Computer Math. 26 (1989), 91\u201399","journal-title":"J. Computer Math"},{"key":"1_CR171","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(92)90211-W","volume":"93","author":"S V\u00e1gv\u00f6lgyi","year":"1992","unstructured":"V\u00e1gv\u00f6lgyi, S.:Top-down tree transducers with two-way tree walking look-ahead. Theoret. Comput. Sci. 93 (1992), 43\u201374","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR172","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0304-3975(93)90127-F","volume":"115","author":"S V\u00e1gv\u00f6lgyi","year":"1993","unstructured":"V\u00e1gv\u00f6lgyi, S.: A fast algorithm for constructing a tree automaton recognizing a congruential tree language. Theoret. Comput. Sci. 115 (1993), 391\u2013399","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR173","first-page":"153","volume":"8","author":"S V\u00e1gv\u00f6lgyi","year":"1987","unstructured":"V\u00e1gv\u00f6lgyi, S., F\u00fcl\u00f6p, Z.: An infinite hierarchy of tree transformations in the class NDR.. Acta Cybern. 8 (1987), 153\u2013168","journal-title":"Acta Cybern"},{"key":"1_CR174","first-page":"33","volume":"6","author":"J. Vir\u00e1gh","year":"1980","unstructured":"Vir\u00e1gh, J.: Deterministic ascending tree automata. I. Acta Cybern. 5 (1980), 33\u201345; II.ibid\n                     6 (1983), 291\u2013301","journal-title":"II.ibid"},{"key":"1_CR175","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-76771-5","volume-title":"Universal algebra for computer scientists","author":"W Wechler","year":"1992","unstructured":"Wechler, W.: Universal algebra for computer scientists. Springer-Verlag, Berlin 1992"},{"key":"1_CR176","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/3-540-56939-1_85","volume-title":"Algebras for classifying tree languages. Automata, Languages and Programming","author":"T Wilke","year":"1993","unstructured":"Wilke, Th.: Algebras for classifying tree languages. Automata, Languages and Programming (Proc. 20th ICALP), Lect. Notes Comput. Sci. 668, Springer-Verlag, Berlin 1993, 347\u2013358"},{"key":"1_CR177","first-page":"167","volume":"4","author":"Z Zachar","year":"1979","unstructured":"Zachar, Z.: The solvability of the equivalence problem for deterministic frontier-to-root tree transducers. Acta Cybern. 4 (1979), 167\u2013177","journal-title":"Acta Cybern"}],"container-title":["Handbook of Formal Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-59126-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T12:21:00Z","timestamp":1768220460000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-59126-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783642638596","9783642591266"],"references-count":177,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-59126-6_1","relation":{},"subject":[],"published":{"date-parts":[[1997]]}}}