Author name cluster

Dmitry Berdinsky

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

TCS Journal 2023 Journal Article

String compression in FA–presentable structures

Dmitry Berdinsky
Sanjay Jain
Bakhadyr Khoussainov
Frank Stephan

We construct a FA–presentation ψ: L → N of the structure ( N; S ) for which a numerical characteristic r ( n ) defined as the maximum number ψ ( w ) for all strings w ∈ L of length less than or equal to n grows faster than any tower of exponents of a fixed height. This result leads us to a more general notion of a compressibility rate defined for FA–presentations of any FA–presentable structure. We show the existence of FA–presentations for the configuration space of a Turing machine and Cayley graphs of some groups for which it grows faster than any tower of exponents of a fixed height. For FA–presentations of the Presburger arithmetic ( N; + ) we show that it is bounded from above by a linear function.

Details DOI

I&C Journal 2022 Journal Article

Cayley polynomial–time computable groups

Dmitry Berdinsky
Murray Elder
Prohrak Kruengthomya

We propose a new generalization of Cayley automatic groups, varying the time complexity of computing multiplication, and language complexity of the normal form representatives. We first consider groups which have normal form language in the class C and multiplication by generators computable in linear time on a certain restricted Turing machine model (position–faithful one–tape). We show that many of the algorithmic properties of automatic groups are preserved, prove various closure properties, and show that the class is quite large. We then generalize to groups which have normal form language in the class C and multiplication by generators computable in polynomial time on a (standard) Turing machine. Of particular interest is when C = REG (the class of regular languages). We prove that REG –Cayley polynomial–time computable groups include all finitely generated nilpotent groups, the wreath product Z 2 ≀ Z 2, and Thompson's group F.

Details DOI