Vladimir Yankovskiy - Groups with context-free Diophantine problem
gcc:7347 - journal of Groups, complexity, cryptology, August 26, 2021, Volume 13, Issue 1 - https://doi.org/10.46298/jgcc.2021.13.1.7347Groups with context-free Diophantine problemArticle
Authors: Vladimir Yankovskiy 
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.
Comment: 6 pages
Source: arXiv.org:2102.00859
Volume: Volume 13, Issue 1
Published on: August 26, 2021
Accepted on: August 25, 2021
Submitted on: April 11, 2021
Keywords: Mathematics - Group Theory, Computer Science - Formal Languages and Automata Theory, 20F10 (Primary) 03D40, 20F70 (Secondary), F.4.3
Classifications
Mathematics Subject Classification 20201
- 03D40 - Word problems, etc. in computability and recursion theory
- 03D55 - Hierarchies of computability and definability
- 20F05 - Generators, relations, and presentations of groups
- 20F10 - Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
- 20F70 - Algebraic geometry over groups; equations over groups
- 68Q45 - Formal languages and automata
Publications
Consultation statistics
This page has been seen 729 times.
This article's PDF has been downloaded 1266 times.