No Access

A MEALY MACHINE WITH POLYNOMIAL GROWTH OF IRRATIONAL DEGREE

LAURENT BARTHOLDI

École Polytechnique Fédérale de Lausanne (EPFL), Institut de Mathématiques B (IMB), CH-1015 Lausanne, Switzerland

Search for more papers by this author

and

ILLYA I. REZNYKOV

École Polytechnique Fédérale de Lausanne (EPFL), Institut de Mathématiques B (IMB), CH-1015 Lausanne, Switzerland

Search for more papers by this author

https://doi.org/10.1142/S0218196708004287Cited by:3 (Source: Crossref)

Abstract

We consider a very simple Mealy machine (two nontrivial states over a two-symbol alphabet), and derive some properties of the semigroup it generates. It is an infinite, finitely generated semigroup, and we show that the growth function of its balls behaves asymptotically like ℓ^α, for ; that the semigroup satisfies the identity g⁶ = g⁴; and that its lattice of two-sided ideals is a chain.

Keywords:

References

L. Bartholdi, Int. Math. Res. Notices 1049 (1998), arXiv.org/math.GR/0012108 DOI: 10.1155/S1073792898000622. Web of Science, Google Scholar
L. Bartholdi, Int. J. Algebra Comput. 11(1), 73 (2001), arXiv.org/math.GR/9910068 DOI: 10.1142/S0218196701000395. Link, Web of Science, Google Scholar
L. Bartholdi, I. I. Reznykov and V. I. Sushchansky, J. Algebra 295(2), 387 (2006), arXiv.org/math.GR/0407312. Crossref, Web of Science, Google Scholar
A. G. Abercrombie, Math. Proc. Cambridge Philos. Soc. 116(2), 209 (1994). Crossref, Web of Science, Google Scholar
A. Ya. Belov and I. A. Ivanov, Acta Appl. Math. 85(1–3), 49 (2005), MR 2128898 (2005m:20138) DOI: 10.1007/s10440-004-5585-5. Crossref, Web of Science, Google Scholar
A. Ya. Belov, Commun. Algebra 31(2), 673 (2003), MR 1968920 (2004a:20064) DOI: 10.1081/AGB-120017339. Crossref, Web of Science, Google Scholar
D. B. A. Epstein et al. , Word Processing in Groups ( Jones and Bartlett Publishers , 1992 ) . Crossref, Google Scholar
I. M. Gel'fand and A. A. Kirillov, Dokl. Akad. Nauk SSSR 167, 503 (1966). Google Scholar
R. I. Grigorchuk, On Burnside's problem on periodic groups, ФункционалАналиПриложен 14(1) (1980) 53–54. English translation: Functional Anal. Appl. 14 (1980) 41–43 . Google Scholar
R. I. Grigorchuk, Dokl. Akad. Nauk SSSR 271(1), 30 (1983). Google Scholar
G. R. Krause and T. H. Lenagan , Growth of Algebras and Gelfand-Kirillov Dimension , Graduate Studies in Mathematics 22 ( American Mathematical Society , Providence, RI , 2000 ) . Google Scholar
A. A. Lavrik-Männlin, Int. J. Algebra Comput. 11(5), 565 (2001), DOI: 10.1142/S021819670100067X. Link, Web of Science, Google Scholar
Y. G. Leonov, Mat. Zametki 67(3), 475 (2000). Crossref, Google Scholar
I. I. Reznykov and V. I. Sushchansky, J. Algebra 304, 712 (2006), DOI: 10.1016/j.jalgebra.2006.03.039. Crossref, Web of Science, Google Scholar
L. M. Shneerson, J. Algebra 235(2), 484 (2001), DOI: 10.1006/jabr.2000.8503. Crossref, Web of Science, Google Scholar
R. B. Warfield Jr., Math. Z. 185(4), 441 (1984), MR 733766 (85f: 17006) DOI: 10.1007/BF01236255. Crossref, Web of Science, Google Scholar