On the 3-state Mealy automata over an m-symbol alphabet of growth order [n^ n/2 m].

In their previous paper [Math. Notes 72, No. 1, 90-104 (2002); translation from Mat. Zametki 72, No. 1, 102-117 (2002; Zbl 1027.20048)], the authors gave a two-state Mealy automaton \(I_2\) with intermediate growth \([\exp\sqrt n]\) and raised the question of the existence of automata with growth strictly between polynomial and \(\exp\sqrt n\). In the present paper they exhibit a 3-state Mealy automaton \(J_m\) over an \(m\)-letter alphabet and show that the growth of \(J_m\) is equal to \([n^{(\log n)/(2\log m)}]\). They give a presentation of the semigroup \(S_m\) associated with \(J_m\) and show that the equalities \([\gamma_{J_m}]=[\gamma_{S_m}]=[n^{(\log n)/(2\log m)}]\) hold for the growths of \(J_m\) and \(S_m\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: On the 3-state Mealy automata over an \(m\)-symbol alphabet of growth order \([n^{\log n/2\log m}]\).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855332)