×

Complete involutive rewriting systems. (English) Zbl 1128.68044

Summary: Given a monoid string rewriting system \(M\), one way of obtaining a complete rewriting system for \(M\) is to use the classical Knuth-Bendix critical pairs completion algorithm. It is well-known that this algorithm is equivalent to computing a noncommutative Gröbner basis for \(M\). This article develops an alternative approach, using noncommutative involutive basis methods to obtain a complete involutive rewriting system for \(M\).

MSC:

68Q42 Grammars and rewriting systems
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buchberger, B., An algorithmic criterion for the solvability of a system of algebraic equations., (Buchberger, B.; Winkler, F., Gröbner Bases and Applications. Gröbner Bases and Applications, Proc. London Math. Soc., vol. 251 (1998), Cambridge University Press), 535-545, Translation of Ph.D. thesis by M. Abramson and R. Lumbert · Zbl 0906.13007
[2] Evans, G.A., 2005. Noncommutative Involutive Bases. Ph.D. Thesis, University of Wales, Bangor; Evans, G.A., 2005. Noncommutative Involutive Bases. Ph.D. Thesis, University of Wales, Bangor
[3] Evans, G.A., 2006. Pedwar: A collection of four programs for computing Gröbner or involutive bases for polynomial ideals over commutative and noncommutative polynomial rings. URL: http://www.dilan4.com/maths/; Evans, G.A., 2006. Pedwar: A collection of four programs for computing Gröbner or involutive bases for polynomial ideals over commutative and noncommutative polynomial rings. URL: http://www.dilan4.com/maths/
[4] Gerdt, V. P., Involutive algorithms for computing Gröbner bases, (Cojocaru, S.; Pfister, G.; Ufnarovski, V., Computational Commutative and Non-Commutative Algebraic Geometry. Computational Commutative and Non-Commutative Algebraic Geometry, NATO Science Series: Computer and Systems Sciences, vol. 196 (2005), IOS Press), 199-225 · Zbl 1104.13012
[5] Gerdt, V. P.; Blinkov, Yu. A., Involutive bases of polynomial ideals, Math. Comput. Simul., 45, 5-6, 519-541 (1998) · Zbl 1017.13500
[6] Gerdt, V. P.; Blinkov, Yu. A., Minimal involutive bases, Math. Comput. Simul., 45, 5-6, 543-560 (1998) · Zbl 1017.13501
[7] Gerdt, V. P.; Blinkov, Yu. A.; Yanovich, D. A., Construction of Janet Bases II. Polynomial Bases, (Ghanzha, V. G.; Mayr, E. W.; Vorozhtsov, E. V., Computer Algebra in Scientific Computing, CASC 2001 (2001), Springer-Verlag: Springer-Verlag Berlin), 249-263 · Zbl 1015.13013
[8] Heyworth, A., Rewriting as a special case of Gröbner basis theory, (Atkinson, M.; Gilbert, N. D.; Howie, J.; Linton, S. A.; Robertson, E. F., Computational and Geometric Aspects of Modern Algebra (Edinburgh, 1998). Computational and Geometric Aspects of Modern Algebra (Edinburgh, 1998), Proc. London Math. Soc., vol. 275 (2000), Cambridge University Press), 101-105 · Zbl 0996.16034
[9] Heyworth, A.; Wensley, C. D., Logged rewriting and identities among relators, (Campbell, C. M.; Robertson, E. F.; Smith, G. C., Groups St. Andrews 2001 in Oxford. Groups St. Andrews 2001 in Oxford, London Math. Soc. Lecture Note Series, vol. 304 (2003), Cambridge University Press), 256-276 · Zbl 1049.20020
[10] Knuth, D. E.; Bendix, P. B., Simple word problems in universal algebras, (Leech, J., Computational Problems in Abstract Algebra (1970), Pergamon Press), 263-297 · Zbl 0188.04902
[11] Mora, T., Gröbner bases for non-commutative polynomial rings, (Calmet, J., AAECC-3: Proc. 3rd Int. Conf. on Algebraic Algorithms and Error-Correcting Codes (Grenoble, France, July 15-19, 1985). AAECC-3: Proc. 3rd Int. Conf. on Algebraic Algorithms and Error-Correcting Codes (Grenoble, France, July 15-19, 1985), Lecture Notes in Comput. Sci., vol. 223 (1986), Springer), 353-362
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.