PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 1 | 23-53
Tytuł artykułu

On the solidity of general varieties of tree languages

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Twórcy
  • Department of Mathematics, University of Turku, FIN-20014 Turku, Finland
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmal_1189
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.