Showing 2021Show all
3 papers · 1 filter
math.GR2021
The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups
J. C. Birget, A. L. Talambutsa
We define the symmetric Post Correspondence Problem (PCP) and prove that it is undecidable. As an application we show that the original proof of undecidability of the freeness prob…
math.GR2021
Efficient computations with counting functions on free groups and free monoids
Tobias Hartnick, Alexey Talambutsa
We present efficient algorithms to decide whether two given counting functions on non-abelian free groups or monoids are at bounded distance from each other and to decide whether t…
math.CO2021
On free semigroups of affine maps on the real line
Alexander Kolpakov, Alexey Talambutsa
In this note we generalise some of the work of Klarner on free semigroups of affine maps acting on the real line by using a classical approach from geometric group theory (the Ping…