Groups with context-free Diophantine problem

Abstract

We find algebraic conditions on a group equivalent to the position of its Diophantine problem in the Chomsky Hierarchy. In particular, we prove that a finitely generated group has a context-free Diophantine problem if and only if it is finite.

Keywords

• mathematics - group theory
• computer science - formal languages and automata theory
• 20f10 (primary) 03d40, 20f70 (secondary)
• f.4.3