No Access

Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids

Centro de Matemática e Aplicações, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829–516 Caparica, Portugal

Search for more papers by this author

Robert D. Gray

School of Mathematics, University of East Anglia, Norwich NR4 7TJ, UK

Search for more papers by this author

, and

António Malheiro

Departamento de Matemática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, 2829–516 Caparica, Portugal

Centro de Álgebra da Universidade de Lisboa, Av. Prof. Gama Pinto 2, 1649–003 Lisboa, Portugal

Search for more papers by this author

https://doi.org/10.1142/S0218196715400044Cited by:9 (Source: Crossref)

Abstract

This paper studies complete rewriting systems and biautomaticity for three interesting classes of finite-rank homogeneous monoids: Chinese monoids, hypoplactic monoids, and sylvester monoids. For Chinese monoids, we first give new presentations via finite complete rewriting systems, using more lucid constructions and proofs than those given independently by Chen & Qui and Güzel Karpuz; we then construct biautomatic structures. For hypoplactic monoids, we construct finite complete rewriting systems and biautomatic structures. For sylvester monoids, which are not finitely presented, we prove that the standard presentation is an infinite complete rewriting system, and construct biautomatic structures. Consequently, the monoid algebras corresponding to monoids of these classes are automaton algebras in the sense of Ufnarovskij.

Dedicated to Stuart W. Margolis on the occasion of his 60th birthday

Keywords:

AMSC: 20M05, 68Q45, 05E05

References

F. Baader and T. Nipkow , Term Rewriting and All That ( Cambridge University Press , Cambridge , 1998 ) . Crossref, Google Scholar
J. Berstel , Transductions and Context-Free Languages , Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics] 38 ( B. G. Teubner , Stuttgart , 1979 ) . Crossref, Google Scholar
A. J. Cain, R. D. Gray and A. Malheiro, On finite complete rewriting systems, finite derivation type, and automaticity for homogeneous monoids, submitted , arXiv: 1407.7428 . Google Scholar
A. J. Cain , R. D. Gray and A. Malheiro , J. Algebra 423 , 37 ( 2015 ) . Crossref, Web of Science, Google Scholar
A. J. Cain and A. Malheiro, Deciding conjugacy in sylvester monoids and other homogeneous monoids, submitted , arXiv: 1404.2618 . Google Scholar
C. M. Campbellet al., Theoret. Comput. Sci. 250(2), 365 (2001). Crossref, Web of Science, Google Scholar
J. Cassaigneet al., Internat. J. Algebra Comput. 11(3), 301 (2001). Link, Web of Science, Google Scholar
F. Cedó and J. Okniński, Algebr. Represent. Theory 16(4), 905 (2013). Crossref, Web of Science, Google Scholar
Y. Chen and J. Qiu, J. Algebra Appl. 7(5), 623 (2008). Link, Web of Science, Google Scholar
G. Duchamp and D. Krob, Words, Languages and Combinatorics, II (World Scientific Publisher, River Edge, NJ, 1994) pp. 124–142. Google Scholar
A. J. Duncan, E. F. Robertson and N. Ruškuc, Math. Proc. Cambridge Philos. Soc. 127(3), 403 (1999). Crossref, Web of Science, Google Scholar
D. B. A. Epstein et al. , Word Processing in Groups ( Jones & Bartlett , Boston, Mass. , 1992 ) . Crossref, Google Scholar
C. Frougny and J. Sakarovitch, Theor. Comput. Sci. 108(1), 45 (1993). Crossref, Web of Science, Google Scholar
E. Güzel Karpuz, Appl. Math. Sci. (Ruse) 4(24), 1081 (2010). Google Scholar
A. Heyworth, Computational and Geometric Aspects of Modern Algebra, London Mathematical Society, Lecture Note Series 275 (Cambridge University Press, Cambridge, 2000) pp. 101–105. Crossref, Google Scholar
F. Hivert, J. C. Novelli and J. Y. Thibon, Theor. Comput. Sci. 339(1), 129 (2005). Crossref, Web of Science, Google Scholar
M. Hoffmann and R. M. Thomas, Fundamentals of Computation Theory, Lecture Notes in Computer Science 3623 (Springer, Berlin, 2005) pp. 56–67. Crossref, Google Scholar
J. E. Hopcroft and J. D. Ullman , Introduction to Automata Theory, Languages, and Computation ( Addison–Wesley Publishing Co. , Reading, Mass. , 1979 ) . Google Scholar
J. Jaszuńska and J. Okniński, Comm. Algebra 34(8), 2745 (2006). Crossref, Web of Science, Google Scholar
J. Jaszuńska and J. Okniński , J. Algebra 346 , 31 ( 2011 ) . Crossref, Web of Science, Google Scholar
D. Krob and J. Y. Thibon, J. Algebraic Combin. 6(4), 339 (1997). Crossref, Web of Science, Google Scholar
J. L. Loday and M. O. Ronco, Adv. Math. 139(2), 293 (1998). Crossref, Web of Science, Google Scholar
M. Lothaire , Algebraic Combinatorics on Words , Encyclopedia of Mathematics and Its Applications 90 ( Cambridge University Press , Cambridge , 2002 ) . Crossref, Google Scholar
J. C. Novelli, Discrete Math. 217(3), 315 (2000). Crossref, Web of Science, Google Scholar
F. Otto, Semigroup Forum 29(2), 223 (1984). Crossref, Web of Science, Google Scholar
V. A. Ufnarovskij, Algebra, VI, Encyclopaedia of Mathematical Sciences 57 (Springer, Berlin, 1995) pp. 1–196. Crossref, Google Scholar