×

Semigroups of linear tree languages. (English) Zbl 1491.20140

Summary: A linear tree language of type \(\tau\) is a set of linear terms, terms in which each variable occurs at most once, of that type. We investigate a semigroup consisting of the collection of all linear tree languages such that products of any element in the collection are nonempty and the operation of the corresponding linear product especially idempotent elements, Green’s relations \(\mathcal{H}\), \(\mathcal{D}\), and \(\mathcal{J}\), and some of its subsemigroups. We discover that this semigroup is neither factorizable nor locally factorizable. We also study the linear product iteration and show that any iteration is idempotent in this semigroup. Moreover, we study a semigroup with the complement of the universe set of the above semigroup together with the same linear product operation.

MSC:

20M35 Semigroups in automata theory, linguistics, etc.
08A70 Applications of universal algebra in computer science
20M10 General structure theory for semigroups
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chajda, I.; Czédli, G.; Halas̆, R.; Lipparini, P., Tolerances as images of congruences in varieties defined by linear identities, Algebra Universalis, 69, 167-169, (2013) · Zbl 1287.08003
[2] Changphas, T.; Denecke, K.; Pibaljommee, B., Linear terms and linear hypersubstitutions, Southeast Asian Bull. Math., 40, (2016)
[3] Th. Changphas, K. Denecke and B. Pibaljommee, The monoid of linear hypersubstitutions, preprint (2016).
[4] Couceiro, M.; Lehtonen, E., Galois theory for sets of operations closed under permutation, cylindrification, and composition, Algebra Universalis, 67, 273-297, (2012) · Zbl 1257.08002
[5] Dapić, P.; Jez̆ek, J.; Marković, P.; McKenzie, R.; Stanovský, D., Star-linear equational theories of groupoids, Algebra Universalis, 56, 357-397, (2007) · Zbl 1127.03023
[6] Denecke, K., The partial clone of linear terms, Sib Math J., 57, 589-598, (2016) · Zbl 1351.08002
[7] Denecke, K.; Glubudom, P., Contributions to General Algebra, Generalized power Menger algebras and generalized non-deterministic hypersubstitutions, 61-70, Verlag Johannes Heyn: Verlag Johannes Heyn, Klagenfurth · Zbl 1107.08005
[8] Denecke, K.; Sarasit, N., Products of tree languages, Bull. Sect. Logic Univ. Lódź, 40, 13-36, (2011) · Zbl 1286.68277
[9] Denecke, K.; Wismath, S. L., Universal Algebra and Applications in Theoretical Computer Science, (2002), Chapman & Hall/CRC: Chapman & Hall/CRC, Boca Raton · Zbl 0993.08001
[10] Gécseg, F.; Steinby, M., Tree Automata, (1984), Akadémiai Kiadó: Akadémiai Kiadó, Budapest
[11] P. Jampachon, Locally factorizable transformation semigroups, Master Science thesis in Mathematics, The Graduate School, Chulalongkorn University, Thailand (1984).
[12] Jampachon, P.; Saichalee, M.; Sullivan, R. P., Locally factorisable transformation semigroups., SEAMS Bull. Math., 25, 233-244, (2001) · Zbl 0995.20045
[13] Kitpratyakul, P.; Pibaljommee, B., A generalized superposition of linear tree languages and products of linear tree languages, Asian-Eur. J. Math., (2017) · Zbl 1400.68108
[14] Lekkoksung, N.; Jumpachon, P., Non-deterministic linear hypersubstitutions, Discuss. Math. Gen. Algebra Appl., 35, 97-103, (2015)
[15] Pilitowska, A., Linear identities in graph algebras, Comment. Math. Univ. Carolin., 50, 11-24, (2009) · Zbl 1212.08004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.