The rank conjecture for groups recognised by Cho automata

About 20 years old · traced to

Let HH be a group and let kk be a nonnegative integer. A kk-counter Cho automaton is a Cho automaton with kk counters whose accepted language includes the word problem of HH. A group is virtually free abelian of rank kk if it has a finite-index free abelian subgroup of rank kk.

Rank conjecture. If the word problem of HH is accepted by a 2k2k-counter or (2k+1)(2k+1)-counter Cho automaton, then HH is virtually free abelian of rank kk.

This is the proposed strengthening of the lower-bound statement discussed immediately beforehand: the known argument gives virtual free abelianness of rank at most the counter parameter, while this conjecture predicts an exact rank under the stated 2k2k- or (2k+1)(2k+1)-counter hypothesis. The source gives no resolution.

References

Primary source

Murray Elder, Mark Kambites and Gretchen Ostheimer, “On groups and counter automata”, arXiv:math/0611188 (2006).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.