×

Effective codescent morphisms in the varieties determined by convergent term rewriting systems. (English) Zbl 1337.08004

Summary: It is shown that the elements of amalgamated free products in a variety of universal algebras have unique normal forms if the variety is represented by a confluent term rewriting system satisfying some additional requirements for its signature and rules. Applying this fact it is proved that any codescent morphism is effective in such varieties. In particular, this is the case for the variety of Mal’tsev algebras, the varieties of magmas with unit and two-sided inverses, idempotent quasigroups, unipotent quasigroups, left Steiner loops, and right Steiner loops.

MSC:

08B25 Products, amalgamated products, and other kinds of limits and colimits
18A20 Epimorphisms, monomorphisms, special classes of morphisms, null morphisms
68Q42 Grammars and rewriting systems
18C20 Eilenberg-Moore and Kleisli constructions for monads
08B05 Equational logic, Mal’tsev conditions
08A70 Applications of universal algebra in computer science
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] F. Baader and T. Nipkow, Term rewriting and all that, Cambridge University Press, 2006. · Zbl 0948.68098
[2] L. Bachmair, N. Dershowitz and J. Hsiang, Orderings for equational proofs, In 1st IEEE Symp. on Logic in Computer Science, 346-357. IEEE Computer Society Press, 1986.
[3] J. Corbin and M. Bidoit, A rehabilitation of Robinson’s unification algorithm, In R. Pavon, editor, Information Processing 83, 909-914, North-Holland, 1983.
[4] N. Dershowitz, L. Marcus and A. Tarlecki, Existence, uniqueness, and construction of rewrite systems, SIAM J. Computing 17 (1988), 629-639. · Zbl 0658.68029
[5] Ph. Dwinger and F. M. Yaqub, Generalized free products of Boolean algebras with an amalgamated subalgebra, Neder. Akad. Wetensch. Proc. Ser. A 66 = Indag. Math. 25(1963), 225-231. · Zbl 0122.26102
[6] T. Evans, On mutiplicative systems defined by generators and relations. I. Normal forms theorems, Proc. Cambridge Philos. Soc. 47(1951), 637-649. · Zbl 0043.02001
[7] J. Gallier, P. Narendran, D. Plaisted, S. Raatz and W. Snyder, An algorithm for finding canonical sets of ground rewrite rules in polinomial time, J. ACM 40 (1993), 1-16. · Zbl 0779.68050
[8] W. Gehrke, Detailed catalogue of canonical term rewriting systems generated automatically, Technical report no. 62, Research Institute for Symbolic Computation (RISC), Johannes Lepler University Linz, 1992.
[9] J. Herbrand, Logical writings, Reidel, 1971.
[10] G. Huet, A complete proof of correctness of the Knuth-Bendix completion procedure, J. Computer and System Sciences, 23 (1981), 11-21, · Zbl 0465.68014
[11] G. Janelidze and W. Tholen, Facets of descent, I. Appl. Categ. Struct. 2 (1994), 1-37. · Zbl 0805.18005
[12] G. Janelidze and W. Tholen, Facets of descent, III: monadic descent for rings and algebras. Appl. Categ. Structures 12(5-6) (2004), 461-477. · Zbl 1078.18007
[13] E. W. Kiss, L. Márki, P. Pröhle and W. Tholen, Categorical algebraic properties. A compendium on amalgamation, congruence extension, epimorphisms, residual smallness and injectivity, Studia Sci. Math. Hungarica 18 (1983), 79-141.
[14] D. E. Knuth and P.B. Bendix, Simple word problems in universal algebra, In. J. Leech, editor, Computational Problems in Abstract Algebra, 263-297, Pergamon Press, 1970. · Zbl 0188.04902
[15] A. Martelli and U. Montanari, An efficient unification algorithm, ACM Trans. Programming Languages and Systems, 4(2) (1982) 258-282. · Zbl 0478.68093
[16] B. Mesablishvili, Pure morphisms of commutative rings are effective descent morphisms for modules - a new proof, Theory Appl. Categ. 7 (2000), no. 3, 38-42. · Zbl 0937.13002
[17] M.H.A. Newman, On theories with a combinatorial definition of “equivalence”, Annals of Mathematics 43(2) (1942), 223-243. · Zbl 0060.12501
[18] M. S. Paterson and M. N. Wegman, Linear unification, J. Computer and System Sciences, 16 (1978), 158-167. · Zbl 0371.68013
[19] R. Socher-Ambrosius, Boolean algebra admits no convergent term rewriting system, In R. E. Book, editor, Proceedings 4th Conference on Rewriting Techniques and Applications, Como (Italy), Lecture Notes in Computer Science488 (1991), 264-274.
[20] D. Zangurashvili, The strong amalgamation property and (effective) codescent morphisms, Theory Appl. Categ. 11 (2003), n. 20, 438-449. · Zbl 1035.18001
[21] D. Zangurashvili, Effective codescent morphisms in some varieties of universal algebras, Appl. Categ. Struct. 22 (2014), 241-252. · Zbl 1303.18010
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.