×

Topological rewriting systems applied to standard bases and syntactic algebras. (English) Zbl 1461.68097

Summary: We introduce topological rewriting systems as a generalisation of abstract rewriting systems, where we replace the set of terms by a topological space. Abstract rewriting systems correspond to topological rewriting systems for the discrete topology. We introduce the topological confluence property as an approximation of the confluence property. Using a representation of linear topological rewriting systems with continuous reduction operators, we show that the topological confluence property is characterised by lattice operations. Using this characterisation, we show that standard bases induce topologically confluent rewriting systems on formal power series. Finally, we investigate duality for reduction operators that we relate to series representations and syntactic algebras. In particular, we use duality for proving that an algebra is syntactic or not.

MSC:

68Q42 Grammars and rewriting systems
13F25 Formal power series rings
16S36 Ordinary and skew polynomial rings and semigroup rings
68Q70 Algebraic theory of languages and automata

Software:

TenRes; operads
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anick, David J., On the homology of associative algebras, Trans. Am. Math. Soc., 296, 2, 641-659 (1986) · Zbl 0598.16028
[2] Baader, Franz; Nipkow, Tobias, Term Rewriting and All That (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0948.68098
[3] Becker, Thomas, Stability and Buchberger criterion for standard bases in power series rings, J. Pure Appl. Algebra, 66, 3, 219-227 (1990) · Zbl 0707.13008
[4] Berger, Roland, Confluence and Koszulity, J. Algebra, 201, 1, 243-283 (1998) · Zbl 0915.16025
[5] Berger, Roland, Koszulity for nonquadratic algebras, J. Algebra, 239, 2, 705-734 (2001) · Zbl 1035.16023
[6] Bergman, George M., The diamond lemma for ring theory, Adv. Math., 29, 2, 178-218 (1978) · Zbl 0326.16019
[7] Bokut’, Leonid A., Imbeddings into simple associative algebras, Algebra Log., 15, 2, 117-142 (1976), 245 · Zbl 0349.16007
[8] Buchberger, Bruno, A theoretical basis for the reduction of polynomials to canonical forms, ACM SIGSAM Bull., 10, 3, 19-29 (1976)
[9] Chenavier, Cyrille, Confluence algebras and acyclicity of the Koszul complex, Algebr. Represent. Theory, 19, 3, 679-711 (2016) · Zbl 1347.18004
[10] Chenavier, Cyrille, Reduction operators and completion of rewriting systems, J. Symb. Comput., 84, 57-83 (2018) · Zbl 1371.68136
[11] Chenavier, Cyrille, A lattice formulation of the noncommutative \(F_4\) procedure, Int. J. Algebra Comput., 29, 1, 23-40 (2019) · Zbl 1417.06006
[12] Chenavier, Cyrille, Syzygies among reduction operators, J. Pure Appl. Algebra, 223, 2, 721-737 (2019) · Zbl 1445.16020
[13] Dotsenko, Vladimir; Khoroshkin, Anton, Gröbner bases for operads, Duke Math. J., 153, 2, 363-396 (2010) · Zbl 1208.18007
[14] Faggian, Claudia, Probabilistic rewriting: normalization, termination, and unique normal forms, (4th International Conference on Formal Structures for Computation and Deduction. 4th International Conference on Formal Structures for Computation and Deduction, FSCD 2019 (2019)) · Zbl 1528.68160
[15] Gaussent, Stéphane; Guiraud, Yves; Malbos, Philippe, Coherent presentations of Artin monoids, Compos. Math., 151, 5, 957-998 (2015) · Zbl 1398.20069
[16] Gerritzen, L.; Holtkamp, R., On Gröbner bases of noncommutative power series, Indag. Math. (N. S.), 9, 4, 503-519 (1998) · Zbl 0930.16017
[17] Guiraud, Yves; Hoffbeck, Eric; Malbos, Philippe, Convergent presentations and polygraphic resolutions of associative algebras, Math. Z., 293, 1-2, 113-179 (2019) · Zbl 1423.16008
[18] Guiraud, Yves; Malbos, Philippe, Higher-dimensional normalisation strategies for acyclicity, Adv. Math., 231, 3-4, 2294-2351 (2012) · Zbl 1266.18008
[19] Guiraud, Yves; Malbos, Philippe, Polygraphs of finite derivation type, Math. Struct. Comput. Sci., 28, 2, 155-201 (2018) · Zbl 1396.18004
[20] Hironaka, Heisuke, Resolution of singularities of an algebraic variety over a field of characteristic zero, I, II, Ann. Math. (2), 79, 205-326 (1964) · Zbl 1420.14031
[21] Poor, Jamal Hossein; Raab, Clemens G.; Regensburger, Georg, Algorithmic operator algebras via normal forms in tensor rings, J. Symb. Comput., 85, 247-274 (2018) · Zbl 06789139
[22] Kandri-Rody, A.; Weispfenning, V., Noncommutative Gröbner bases in algebras of solvable type, J. Symb. Comput., 9, 1, 1-26 (1990) · Zbl 0715.16010
[23] Kobayashi, Yuji, Complete rewriting systems and homology of monoid algebras, J. Pure Appl. Algebra, 65, 3, 263-275 (1990) · Zbl 0711.20035
[24] Kriegk, Benoit; Van den Bergh, Michel, Representations of non-commutative quantum groups, Proc. Lond. Math. Soc. (3), 110, 1, 57-82 (2015) · Zbl 1312.16033
[25] Teo, Mora, An introduction to commutative and noncommutative Gröbner bases, Theor. Comput. Sci., 134, 1, 131-173 (1994) · Zbl 0824.68056
[26] Petitot, Michel, Algèbre non commutative en Scratchpad: application au problème de la réalisation minimale analytique (1992), Lille 1, PhD thesis
[27] Priddy, Stewart B., Koszul resolutions, Trans. Am. Math. Soc., 152, 39-60 (1970) · Zbl 0261.18016
[28] Reutenauer, Christophe, Séries formelles et algèbres syntactiques, J. Algebra, 66, 2, 448-483 (1980) · Zbl 0444.68075
[29] Širšov, Anatoly I., Some algorithm problems for Lie algebras, Sib. Mat. Zh., 3, 292-296 (1962) · Zbl 0104.26004
[30] Squier, Craig C., Word problems and a homological finiteness condition for monoids, J. Pure Appl. Algebra, 49, 1-2, 201-217 (1987) · Zbl 0648.20045
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.