Geodesic
On the solidity of general varieties of tree languages
Discussiones Mathematicae. General Algebra and Applications, Tome 32 (2012) no. 1, pp. 23-53.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: varieties of tree languages, solid varieties, hypersubstitutions, tree homomorphisms 
@article{DMGAA_2012_32_1_a1,
     author = {Steinby, Magnus},
     title = {On the solidity of general varieties of tree languages},
     journal = {Discussiones Mathematicae. General Algebra and Applications},
     pages = {23--53},
     publisher = {mathdoc},
     volume = {32},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGAA_2012_32_1_a1/}
}
TY  - JOUR
AU  - Steinby, Magnus
TI  - On the solidity of general varieties of tree languages
JO  - Discussiones Mathematicae. General Algebra and Applications
PY  - 2012
SP  - 23
EP  - 53
VL  - 32
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGAA_2012_32_1_a1/
LA  - en
ID  - DMGAA_2012_32_1_a1
ER  - 
%0 Journal Article
%A Steinby, Magnus
%T On the solidity of general varieties of tree languages
%J Discussiones Mathematicae. General Algebra and Applications
%D 2012
%P 23-53
%V 32
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGAA_2012_32_1_a1/
%G en
%F DMGAA_2012_32_1_a1
Steinby, Magnus. On the solidity of general varieties of tree languages. Discussiones Mathematicae. General Algebra and Applications, Tome 32 (2012) no. 1, pp. 23-53. http://geodesic.mathdoc.fr/item/DMGAA_2012_32_1_a1/

[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

[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

[3] F. Baader and T. Nipkow, Term Rewriting and All That, Cambridge University Press, Cambridge, 1998. doi: 10.1017/CBO9781139172752

[4] P. Baltazar, M-solid varieties of languages, Acta Cybernetica 18 (2008), 719-731.

[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

[6] P.M. Cohn, Universal Algebra (2.ed.), D. Reidel, Dordrecht, 1981. doi: 10.1007/978-94-009-8399-1

[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.

[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.

[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.

[10] K. Denecke and S.L. Wismath, Hyperidentities and Clones, Gordon and Bleach Science Publishers, Singapore, 2000.

[11] K. Denecke and S.L. Wismath, Universal Algebra and Application in Theoretical Computer Science, Chapman Hall/CRC, Boca Raton, 2002.

[12] S. Eilenberg, Automata, Languages, and Machines Vol. B, Academic Press, New York, 1976.

[13] J. Engelfriet, Bottom-up and top-down tree transformations, Mathematical Systems Theory 9 (1975), 198-231. doi: 10.1007/BF01704020

[14] Z. Ésik, Definite tree automata and their cascade composition, Publicationes Mathematicae Debrecen 48 3-4 (1996), 243-261.

[15] Z. Ésik, A variety theorem for trees and theories, Publicationes Mathematicae Debrecen 54 Supplementum (1999), 711-762.

[16] Z. Fülöp and H. Vogler, Syntax-Directed Semantics, Formal Models Based on Tree Transducers, Springer, Berlin, 1998.

[17] F. Gécseg and M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest, 1984.

[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

[19] K. Głazek, Weak homomorphisms of general algebras and related topics, Mathematical Seminar Notes 8 (1980), 1-36.

[20] E. Graczyńska and D. Schweigert, Hypervarieties of a given type, Algebra Universalis 27 (1990), 303-318.

[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.

[22] U. Heuter, Definite tree languages, Bulletin of EATCS 35 (1988), 137-144.

[23] U. Heuter, Zur Klassifizierung regulärer Baumsprachen, Dissertation, Technical University of Aachen, Faculty of Natural Sciences, Aachen, 1989.

[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.

[25] M. Kolibiar, Weak homomorphisms in some classes of algebras, Studia Scientiarum Mathematicarum Hungaria 30 (1984), 413-420.

[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

[27] B. Pibaljommee, M-solid pseudovarieties, Dissertation, University of Potsdam, Potsdam, 2005.

[28] V. Piirainen, Piecewise testable tree languages, TUCS Technical Report 634, Turku Centre for Computer Science, Turku, 2004.

[29] J.E. Pin, Varieties of formal languages, North Oxford Academic Publishers, Oxford, 1986. doi: 10.1007/978-1-4613-2215-3

[30] S. Salehi, Varieties of tree languages definable by syntactic monoids, Acta Cybernetica 17 (2005), 21-41.

[31] K. Salomaa, Syntactic monoids of regular forests (in Finnish). Master's Thesis, Department of Mathematics, University of Turku, Turku, 1983.

[32] D. Schweigert, Hyperidentities, in: Algebras and Orders (eds. I.G. Rosenberg and G. Sabidussi), Kluwer Academic Publishers, Dordrecht, 1993, 405-506.

[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.

[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.

[35] M. Steinby, Generalized varieties of tree languages, Theoretical Computer Science 205 (1998), 1-43. doi: 10.1016/S0304-3975(98)00010-3

[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

[37] J.W. Thatcher, Generalized² sequential machines, Journal of Computer Systems Science 1 (1970), 339-367. doi: 10.1016/S0022-0000(70)80017-4

[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.