For a class of hypersubstitutions 𝓚, we define the 𝓚-solidity of general varieties of tree languages (GVTLs) that contain tree languages over all alphabets, general varieties of finite algebras (GVFAs), and general varieties of finite congruences (GVFCs). We show that if 𝓚 is a so-called category of substitutions, a GVTL is 𝓚-solid exactly in case the corresponding GVFA, or the corresponding GVFC, is 𝓚-solid. We establish the solidity status of several known GVTLs with respect to certain categories of substitutions derived from some important classes of tree homomorphisms.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmal_1189,
author = {Magnus Steinby},
title = {On the solidity of general varieties of tree languages},
journal = {Discussiones Mathematicae - General Algebra and Applications},
volume = {32},
year = {2012},
pages = {23-53},
zbl = {1306.08004},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmal_1189}
}
Magnus Steinby. On the solidity of general varieties of tree languages. Discussiones Mathematicae - General Algebra and Applications, Tome 32 (2012) pp. 23-53. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmal_1189/
[000] [1] J. Almeida, On pseudovarieties, varieties of languages, filters of congruences, pseudoidentities and related topics, Algebra Universalis 27 (1990), 333-350. doi: 10.1007/BF01190713 | Zbl 0715.08006
[001] [2] A. Arnold and M. Dauchet, Morphismes et bimorphismes d'arbres, Theoretical Computer Science 13 (1982), 33-93. doi: 10.1016/0304-3975(82)90098-6 | Zbl 0486.68072
[002] [3] F. Baader and T. Nipkow, Term Rewriting and All That, Cambridge University Press, Cambridge, 1998. doi: 10.1017/CBO9781139172752 | Zbl 0948.68098
[003] [4] P. Baltazar, M-solid varieties of languages, Acta Cybernetica 18 (2008), 719-731. | Zbl 1164.68022
[004] [5] S. Burris and H.P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag, New York, 1981. doi: 10.1007/978-1-4613-8130-3 | Zbl 0478.08001
[005] [6] P.M. Cohn, Universal Algebra (2.ed.), D. Reidel, Dordrecht, 1981. doi: 10.1007/978-94-009-8399-1
[006] [7] K. Denecke and J. Koppitz, M-solid positive varieties of tree languages, in: Contributions to General Algebra 19, Verlag Johannes Heyn, Klagenfurth, 2010, 57-80. | Zbl 1244.08002
[007] [8] K. Denecke, D. Lau, R. Pöschel and D. Schweigert, Hyperidentities, hyperequational classes and clone congruences, in: Contributions to General Algebra 7, Verlag Hölder-Pichler-Tempsky, Wien, 1991, 97-118. | Zbl 0759.08005
[008] [9] K. Denecke and M. Reichel, Monoids of hypersubstitutions and M-solid varieties, in: Contributions to General Algebra 9, Verlag B.G. Teubner, Wien, 1995, 117-126. | Zbl 0884.08008
[009] [10] K. Denecke and S.L. Wismath, Hyperidentities and Clones, Gordon and Bleach Science Publishers, Singapore, 2000. | Zbl 0960.08001
[010] [11] K. Denecke and S.L. Wismath, Universal Algebra and Application in Theoretical Computer Science, Chapman & Hall/CRC, Boca Raton, 2002.
[011] [12] S. Eilenberg, Automata, Languages, and Machines Vol. B, Academic Press, New York, 1976.
[012] [13] J. Engelfriet, Bottom-up and top-down tree transformations, Mathematical Systems Theory 9 (1975), 198-231. doi: 10.1007/BF01704020 | Zbl 0335.68061
[013] [14] Z. Ésik, Definite tree automata and their cascade composition, Publicationes Mathematicae Debrecen 48 3-4 (1996), 243-261. | Zbl 0851.68059
[014] [15] Z. Ésik, A variety theorem for trees and theories, Publicationes Mathematicae Debrecen 54 Supplementum (1999), 711-762. | Zbl 0981.68085
[015] [16] Z. Fülöp and H. Vogler, Syntax-Directed Semantics, Formal Models Based on Tree Transducers, Springer, Berlin, 1998.
[016] [17] F. Gécseg and M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest, 1984.
[017] [18] F. Gécseg and M. Steinby, Tree languages, in: Handbook of Formal Languages, Vol. 3 (eds. G. Rozenberg and A. Salomaa), Springer-Verlag, Berlin, 1997, 1-69. doi: 10.1007/978-3-642-59126-6_1
[018] [19] K. Głazek, Weak homomorphisms of general algebras and related topics, Mathematical Seminar Notes 8 (1980), 1-36. | Zbl 0435.08002
[019] [20] E. Graczyńska and D. Schweigert, Hypervarieties of a given type, Algebra Universalis 27 (1990), 303-318. | Zbl 0715.08002
[020] [21] E. Graczyńska, R. Pöschel and M.V. Volkov, Solid pseudovarieties, in: General Algebra and Applications to Discrete Mathematics (eds. K. Denecke and O. Lüders), Shaker Verlag, Aachen, 1997, 93-110.
[021] [22] U. Heuter, Definite tree languages, Bulletin of EATCS 35 (1988), 137-144. | Zbl 0676.68027
[022] [23] U. Heuter, Zur Klassifizierung regulärer Baumsprachen, Dissertation, Technical University of Aachen, Faculty of Natural Sciences, Aachen, 1989.
[023] [24] E. Jurvanen, A. Potthoff and W. Thomas, Tree languages recognizable by regular frontier check, in: Developments in Language Theory (eds. G. Rozenberg and A. Salomaa), World Scientific, Singapore, 1994, 3-17.
[024] [25] M. Kolibiar, Weak homomorphisms in some classes of algebras, Studia Scientiarum Mathematicarum Hungaria 30 (1984), 413-420. | Zbl 0608.08002
[025] [26] J. Koppitz and K. Denecke, M-Solid Varieties of Algebras, Springer Science+Business Media, New York, 2006. doi: 10.1007/0-387-30806-7 | Zbl 1094.08001
[026] [27] B. Pibaljommee, M-solid pseudovarieties, Dissertation, University of Potsdam, Potsdam, 2005.
[027] [28] V. Piirainen, Piecewise testable tree languages, TUCS Technical Report 634, Turku Centre for Computer Science, Turku, 2004. | Zbl 1169.68489
[028] [29] J.E. Pin, Varieties of formal languages, North Oxford Academic Publishers, Oxford, 1986. doi: 10.1007/978-1-4613-2215-3 | Zbl 0632.68069
[029] [30] S. Salehi, Varieties of tree languages definable by syntactic monoids, Acta Cybernetica 17 (2005), 21-41. | Zbl 1084.68078
[030] [31] K. Salomaa, Syntactic monoids of regular forests (in Finnish). Master's Thesis, Department of Mathematics, University of Turku, Turku, 1983.
[031] [32] D. Schweigert, Hyperidentities, in: Algebras and Orders (eds. I.G. Rosenberg and G. Sabidussi), Kluwer Academic Publishers, Dordrecht, 1993, 405-506.
[032] [33] M. Steinby, Syntactic algebras and varieties of recognizable sets, in: Les Arbres en Algèbre et en Programmation, Proc. 4th CAAP, Lille 1979, University of Lille, Lille 1979, 226-240.
[033] [34] M. Steinby, A theory of tree language varieties, in: Tree Automata and Languages (eds. M. Nivat and A. Podelski), North-Holland, Amsterdam, 1992, 57-81. | Zbl 0798.68087
[034] [35] M. Steinby, Generalized varieties of tree languages, Theoretical Computer Science 205 (1998), 1-43. doi: 10.1016/S0304-3975(98)00010-3 | Zbl 0913.68115
[035] [36] M. Steinby, Algebraic classifications of regular tree languages, in: Structural Theory of Automata, Semigroups, and Universal Algebra (eds. V.B. Kudryavtsev and I.G. Rosenberg), Springer, Dordrecht, 2005, 381-432. doi: 10.1007/1-4020-3817-8_13 | Zbl 1092.68060
[036] [37] J.W. Thatcher, Generalized² sequential machines, Journal of Computer Systems Science 1 (1970), 339-367. doi: 10.1016/S0022-0000(70)80017-4
[037] [38] W. Thomas, Logical aspects in the study of tree languages, in: 9th Colloquium on Trees in Algebra and Programming (Proc. 9th CAAP, Bordeaux 1984, ed. B. Courcelle), Cambridge University Press, London, 1984, 31-49.