Download PDF - On the solidity of general varieties of tree languagesAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On the solidity of general varieties of tree languages

Authors 1

Affiliations

  1. Department of Mathematics, University of Turku, FIN-20014 Turku, Finland

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.

Keywords

ENG
varieties of tree languages, solid varieties, hypersubstitutions, tree homomorphisms

Bibliography

  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.
Discussiones Mathematicae - General Algebra and Applications
2012/32/1
Export to PBN, Opens in new tab
Pages:
23-53
Main language of publication
English
Received
2012-09-12
Accepted
2012-11-30
Published
2012

DOI: 10.7151/dmgaa.1189

Exact and natural sciences