×

The additive group of the rationals does not have an automatic presentation. (English) Zbl 1247.03070

Summary: We prove that the additive group of the rationals does not have an automatic presentation. The proof also applies to certain other abelian groups, for example, torsion-free groups that are \(p\)-divisible for infinitely many primes \(p\), or groups of the form \(\oplus _{p \in I} \mathbf Z(p^{\infty })\), where \(I\) is an infinite set of primes.

MSC:

03D05 Automata and formal grammars in connection with logical questions
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

References:

[1] Logical Methods in Computer Science 3 pp 18– (2007)
[2] Bulletin of the European Association for Theoretical Computer Science 94 pp 181– (2008)
[3] Word processing in groups (1992)
[4] Additive combinatorics 105 (2006) · Zbl 1127.11002
[5] Nachala strukturnoi teorii slozheniya mnozhestv (1966)
[6] Logic Colloquium 2007 35 pp 132– (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.