On the solidity of general varieties of tree languages

Magnus Steinby

Discussiones Mathematicae - General Algebra and Applications (2012)

  • Volume: 32, Issue: 1, page 23-53
  • ISSN: 1509-9415

Abstract

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

How to cite

top

Magnus Steinby. "On the solidity of general varieties of tree languages." Discussiones Mathematicae - General Algebra and Applications 32.1 (2012): 23-53. <http://eudml.org/doc/270472>.

@article{MagnusSteinby2012,
abstract = {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.},
author = {Magnus Steinby},
journal = {Discussiones Mathematicae - General Algebra and Applications},
keywords = {varieties of tree languages; solid varieties; hypersubstitutions; tree homomorphisms},
language = {eng},
number = {1},
pages = {23-53},
title = {On the solidity of general varieties of tree languages},
url = {http://eudml.org/doc/270472},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Magnus Steinby
TI - On the solidity of general varieties of tree languages
JO - Discussiones Mathematicae - General Algebra and Applications
PY - 2012
VL - 32
IS - 1
SP - 23
EP - 53
AB - 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.
LA - eng
KW - varieties of tree languages; solid varieties; hypersubstitutions; tree homomorphisms
UR - http://eudml.org/doc/270472
ER -

References

top
  1. [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 Zbl0715.08006
  2. [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 Zbl0486.68072
  3. [3] F. Baader and T. Nipkow, Term Rewriting and All That, Cambridge University Press, Cambridge, 1998. doi: 10.1017/CBO9781139172752 Zbl0948.68098
  4. [4] P. Baltazar, M-solid varieties of languages, Acta Cybernetica 18 (2008), 719-731. Zbl1164.68022
  5. [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 Zbl0478.08001
  6. [6] P.M. Cohn, Universal Algebra (2.ed.), D. Reidel, Dordrecht, 1981. doi: 10.1007/978-94-009-8399-1 
  7. [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. Zbl1244.08002
  8. [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. Zbl0759.08005
  9. [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. Zbl0884.08008
  10. [10] K. Denecke and S.L. Wismath, Hyperidentities and Clones, Gordon and Bleach Science Publishers, Singapore, 2000. Zbl0960.08001
  11. [11] K. Denecke and S.L. Wismath, Universal Algebra and Application in Theoretical Computer Science, Chapman & Hall/CRC, Boca Raton, 2002. 
  12. [12] S. Eilenberg, Automata, Languages, and Machines Vol. B, Academic Press, New York, 1976. 
  13. [13] J. Engelfriet, Bottom-up and top-down tree transformations, Mathematical Systems Theory 9 (1975), 198-231. doi: 10.1007/BF01704020 Zbl0335.68061
  14. [14] Z. Ésik, Definite tree automata and their cascade composition, Publicationes Mathematicae Debrecen 48 3-4 (1996), 243-261. Zbl0851.68059
  15. [15] Z. Ésik, A variety theorem for trees and theories, Publicationes Mathematicae Debrecen 54 Supplementum (1999), 711-762. Zbl0981.68085
  16. [16] Z. Fülöp and H. Vogler, Syntax-Directed Semantics, Formal Models Based on Tree Transducers, Springer, Berlin, 1998. 
  17. [17] F. Gécseg and M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest, 1984. 
  18. [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. [19] K. Głazek, Weak homomorphisms of general algebras and related topics, Mathematical Seminar Notes 8 (1980), 1-36. Zbl0435.08002
  20. [20] E. Graczyńska and D. Schweigert, Hypervarieties of a given type, Algebra Universalis 27 (1990), 303-318. Zbl0715.08002
  21. [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. [22] U. Heuter, Definite tree languages, Bulletin of EATCS 35 (1988), 137-144. Zbl0676.68027
  23. [23] U. Heuter, Zur Klassifizierung regulärer Baumsprachen, Dissertation, Technical University of Aachen, Faculty of Natural Sciences, Aachen, 1989. 
  24. [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. [25] M. Kolibiar, Weak homomorphisms in some classes of algebras, Studia Scientiarum Mathematicarum Hungaria 30 (1984), 413-420. Zbl0608.08002
  26. [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 Zbl1094.08001
  27. [27] B. Pibaljommee, M-solid pseudovarieties, Dissertation, University of Potsdam, Potsdam, 2005. 
  28. [28] V. Piirainen, Piecewise testable tree languages, TUCS Technical Report 634, Turku Centre for Computer Science, Turku, 2004. Zbl1169.68489
  29. [29] J.E. Pin, Varieties of formal languages, North Oxford Academic Publishers, Oxford, 1986. doi: 10.1007/978-1-4613-2215-3 Zbl0632.68069
  30. [30] S. Salehi, Varieties of tree languages definable by syntactic monoids, Acta Cybernetica 17 (2005), 21-41. Zbl1084.68078
  31. [31] K. Salomaa, Syntactic monoids of regular forests (in Finnish). Master's Thesis, Department of Mathematics, University of Turku, Turku, 1983. 
  32. [32] D. Schweigert, Hyperidentities, in: Algebras and Orders (eds. I.G. Rosenberg and G. Sabidussi), Kluwer Academic Publishers, Dordrecht, 1993, 405-506. 
  33. [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. [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. Zbl0798.68087
  35. [35] M. Steinby, Generalized varieties of tree languages, Theoretical Computer Science 205 (1998), 1-43. doi: 10.1016/S0304-3975(98)00010-3 Zbl0913.68115
  36. [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 Zbl1092.68060
  37. [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. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.