The smallest Mealy automaton of intermediate growth.

DOI10.1016/j.jalgebra.2004.08.040zbMath1095.20045arXivmath/0407312MaRDI QIDQ2368724

Laurent Bartholdi, I. I. Reznykov, V. I. Sushchans'kyi

Publication date: 28 April 2006

Published in: Journal of Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0407312

zbMATH Keywords

growth series; growth functions; Mealy automata; semigroups of automatic transformations; semigroups of intermediate growth

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20M05: Free semigroups, generators and relations, word problems

68Q70: Algebraic theory of languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Some topics in the dynamics of group actions on rooted trees., The concept of duality for automata over a changing alphabet and generation of a free group by such automata, On the 3-state Mealy automata over an \(m\)-symbol alphabet of growth order \([n^{\log n/2\log m}\).], Growth of permutational extensions., A software system for growth analysis of Mealy automata, Implementing Computations in Automaton (Semi)groups, INVERSE SEMIGROUPS OF PARTIAL AUTOMATON PERMUTATIONS, A MEALY MACHINE WITH POLYNOMIAL GROWTH OF IRRATIONAL DEGREE

Cites Work

• 2-generated semigroup of automatic transformations whose growth is defined by Fibonacci series.
• Automorphisms of one-rooted trees: growth, circuit structure, and acyclicity.
• Two-state Mealy automata of intermediate growth over a two-letter alphabet
• Number Theory and Semigroups of Intermediate Growth
• Subgroups and subrings of profinite rings
• Hausdorff dimension, pro-𝑝 groups, and Kac-Moody algebras
• ON SOME SEMIGROUPS OF INTERMEDIATE GROWTH
• Asymptotic density and the asymptotics of partition functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item