Dmitry Berdinsky
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Dmitry Berdinsky has a total of 18 co-authors. Here are the top co-authors by number of shared publications:
- Prohrak Kruengthomya
Faculty of Science Mahidol University 10400 Bangkok Thailand
4 shared publications - Cesare Bracco
Department of Mathematics and Computer Science "Ulisse Dini" University of Florence Viale Giovanni Battista Morgagni 67/a 50134 Florence Italy
3 shared publications - Durkbin Cho
Department of Mathematics, Dongguk University, Pil-dong 3-ga, Jung-gu, Seoul 04620, Republic of Korea
3 shared publications - Murray Elder
School of Mathematical and Physical Sciences, University of Technology Sydney, Broadway NSW 2007, Australia
3 shared publications - Tae-Wan Kim
Seoul National University
3 shared publications - Bakhadyr Khoussainov
University of Electronic Science and Technology of China
2 shared publications
Latest Publications
- Open Access
On constant mean curvature surfaces in the Heisenberg group
We study constant mean curvature surfaces in the three-dimensional Heisenberg group. We prove that a constant mean curvature surface in a neighborhood of non-umbilic point is described by some solution of a sinh-Gordon equation subject to a first order differential constraint.
Open AccessOn constant mean curvature surfaces in the Heisenberg group
We study constant mean curvature surfaces in the three-dimensional Heisenberg group. We prove that a constant mean curvature surface in a neighborhood of non-umbilic point is described by some solution of a sinh-Gordon equation subject to a first order differential constraint.
- Open Access
On orthogonal curvilinear coordinate systems in constant curvature spaces
We describe a method for constructing $n$-orthogonal coordinate systems in constant curvature spaces. The construction proposed is a modification of Krichever's method for producing orthogonal curvilinear coordinate systems in the $n$-dimensional Euclidean space. To demonstrate how this method works, we construct examples of orthogonal coordinate systems on the two-dimensional sphere and the hyperbolic plane, in the case when the spectral curve is reducible and all irreducible components are isomorphic to a complex projective line.
Open AccessOn orthogonal curvilinear coordinate systems in constant curvature spaces
We describe a method for constructing $n$-orthogonal coordinate systems in constant curvature spaces. The construction proposed is a modification of Krichever's method for producing orthogonal curvilinear coordinate systems in the $n$-dimensional Euclidean space. To demonstrate how this method works, we construct examples of orthogonal coordinate systems on the two-dimensional sphere and the hyperbolic plane, in the case when the spectral curve is reducible and all irreducible components are isomorphic to a complex projective line.
- 27 June 2024
- Published by World Scientific Pub Co Pte Ltd in Asian-European Journal of Mathematics
- Vol. 17 (10)
Extending the synchronous fellow traveler property
In this paper, we introduce an extension of the fellow traveler property which allows fellow travelers to be at distance bounded from above by a function [ ] growing slower than any linear function. We study normal forms satisfying this extended fellow traveler property and certain geometric constraints that naturally generalize two fundamental properties of an automatic normal form — the regularity of its language and the bounded length difference property. We show examples of such normal forms and prove some nonexistence theorems.
- 27 June 2024
- Published by World Scientific Pub Co Pte Ltd in Asian-European Journal of Mathematics
- Vol. 17 (10)
Extending the synchronous fellow traveler property
In this paper, we introduce an extension of the fellow traveler property which allows fellow travelers to be at distance bounded from above by a function [ ] growing slower than any linear function. We study normal forms satisfying this extended fellow traveler property and certain geometric constraints that naturally generalize two fundamental properties of an automatic normal form — the regularity of its language and the bounded length difference property. We show examples of such normal forms and prove some nonexistence theorems.
- Open Access
Finite Automata Encoding Functions: A Representation Using B-splines
Finite automata are used to encode geometric figures, functions and can be used for image compression and processing. The original approach is to represent each point of a figure (a graph of a function) in $\mathbb{R}^n$ as a convolution of its $n$ coordinates written in some base. Then a figure is said to be encoded as a finite automaton if the set of convolutions corresponding to points in this figure is accepted by a finite automaton. Jurgensen, Staiger and Yamasaki showed that the only continuously differentiable functions which can be encoded as a finite automaton in this way are linear. In this paper we propose a representation which enables to encode piecewise polynomial functions with arbitrary degrees of smoothness that substantially extends a family of functions which can be encoded as finite automata. This representation naturally comes from the framework of hierarchical tensor product B-splines utilized in numerical computational geometry. We show that finite automata provide a simple tool suitable for solving computational problem arising in this framework including the case when the support of a function is unbounded.Open AccessFinite Automata Encoding Functions: A Representation Using B-splines
Finite automata are used to encode geometric figures, functions and can be used for image compression and processing. The original approach is to represent each point of a figure (a graph of a function) in $\mathbb{R}^n$ as a convolution of its $n$ coordinates written in some base. Then a figure is said to be encoded as a finite automaton if the set of convolutions corresponding to points in this figure is accepted by a finite automaton. Jurgensen, Staiger and Yamasaki showed that the only continuously differentiable functions which can be encoded as a finite automaton in this way are linear. In this paper we propose a representation which enables to encode piecewise polynomial functions with arbitrary degrees of smoothness that substantially extends a family of functions which can be encoded as finite automata. This representation naturally comes from the framework of hierarchical tensor product B-splines utilized in numerical computational geometry. We show that finite automata provide a simple tool suitable for solving computational problem arising in this framework including the case when the support of a function is unbounded. - Open Access
String Compression in FA-Presentable Structures
We construct a FA-presentation $ψ: L \rightarrow \mathbb{N}$ of the structure $(\mathbb{N};\mathrm{S})$ for which a numerical characteristic $r(n)$ defined as the maximum number $ψ(w)$ for all strings $w \in 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 $(\mathbb{N};+)$ we show that it is bounded from above by a linear function.Open AccessString Compression in FA-Presentable Structures
We construct a FA-presentation $ψ: L \rightarrow \mathbb{N}$ of the structure $(\mathbb{N};\mathrm{S})$ for which a numerical characteristic $r(n)$ defined as the maximum number $ψ(w)$ for all strings $w \in 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 $(\mathbb{N};+)$ we show that it is bounded from above by a linear function. - Open Access
On the geometry of Cayley automatic groups
In contrast to being automatic, being Cayley automatic \emph{a priori} has no geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a fellow traveler property. Here we study a distance function introduced by the first author and Trakuldit which aims to measure how far a Cayley automatic group is from being automatic, in terms of how badly the Cayley graph fails the fellow traveler property. The first author and Trakuldit showed that if it fails by at most a constant amount, then the group is in fact automatic. In this article we show that for a large class of non-automatic Cayley automatic groups this function is bounded below by a linear function in a precise sense defined herein. In fact, for all Cayley automatic groups which have super-quadratic Dehn function, or which are not finitely presented, we can construct a non-decreasing function which (1) depends only on the group and (2) bounds from below the distance function for any Cayley automatic structure on the group.
Open AccessOn the geometry of Cayley automatic groups
In contrast to being automatic, being Cayley automatic \emph{a priori} has no geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a fellow traveler property. Here we study a distance function introduced by the first author and Trakuldit which aims to measure how far a Cayley automatic group is from being automatic, in terms of how badly the Cayley graph fails the fellow traveler property. The first author and Trakuldit showed that if it fails by at most a constant amount, then the group is in fact automatic. In this article we show that for a large class of non-automatic Cayley automatic groups this function is bounded below by a linear function in a precise sense defined herein. In fact, for all Cayley automatic groups which have super-quadratic Dehn function, or which are not finitely presented, we can construct a non-decreasing function which (1) depends only on the group and (2) bounds from below the distance function for any Cayley automatic structure on the group.
- Open Access
Cayley Polynomial-Time Computable Groups
We propose a new generalisation 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 $\mathcal 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 (quadratic time word problem), prove various closure properties, and show that the class is quite large; for example it includes all virtually polycyclic groups. We then generalise to groups which have normal form language in the class $\mathcal C$ and multiplication by generators computable in polynomial time on a (standard) Turing machine. Of particular interest is when $\mathcal C= \mathrm{REG}$ (the class of regular languages). We prove that $\mathrm{REG}$-Cayley polynomial-time computable groups includes all finitely generated nilpotent groups, the wreath product $\mathbb Z_2 \wr \mathbb Z^2$, and Thompson's group $F$.Open AccessCayley Polynomial-Time Computable Groups
We propose a new generalisation 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 $\mathcal 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 (quadratic time word problem), prove various closure properties, and show that the class is quite large; for example it includes all virtually polycyclic groups. We then generalise to groups which have normal form language in the class $\mathcal C$ and multiplication by generators computable in polynomial time on a (standard) Turing machine. Of particular interest is when $\mathcal C= \mathrm{REG}$ (the class of regular languages). We prove that $\mathrm{REG}$-Cayley polynomial-time computable groups includes all finitely generated nilpotent groups, the wreath product $\mathbb Z_2 \wr \mathbb Z^2$, and Thompson's group $F$. - Open Access
Measuring closeness between Cayley automatic groups and automatic groups
In this paper we introduce a way to estimate a level of closeness of Cayley automatic groups to the class of automatic groups using a certain numerical characteristic. We characterize Cayley automatic groups which are not automatic in terms of this numerical characteristic and then study it for the lamplighter group, the Baumslag--Solitar groups and the Heisenberg group.
Open AccessMeasuring closeness between Cayley automatic groups and automatic groups
In this paper we introduce a way to estimate a level of closeness of Cayley automatic groups to the class of automatic groups using a certain numerical characteristic. We characterize Cayley automatic groups which are not automatic in terms of this numerical characteristic and then study it for the lamplighter group, the Baumslag--Solitar groups and the Heisenberg group.
- 13 April 2021
- Published by Cambridge University Press (CUP) in Bulletin of the Australian Mathematical Society
- Vol. 104 (3) , 464-474
BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
We extend work of Berdinsky and Khoussainov [‘Cayley automatic representations of wreath products’, International Journal of Foundations of Computer Science 27(2) (2016), 147–159] to show that being Cayley automatic is closed under taking the restricted wreath product with a virtually infinite cyclic group. This adds to the list of known examples of Cayley automatic groups.
- 13 April 2021
- Published by Cambridge University Press (CUP) in Bulletin of the Australian Mathematical Society
- Vol. 104 (3) , 464-474
BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
We extend work of Berdinsky and Khoussainov [‘Cayley automatic representations of wreath products’, International Journal of Foundations of Computer Science 27(2) (2016), 147–159] to show that being Cayley automatic is closed under taking the restricted wreath product with a virtually infinite cyclic group. This adds to the list of known examples of Cayley automatic groups.
- Open Access
- 25 February 2020
- Published by Springer Nature
- Vol. 12038, 115-127
Nonstandard Cayley Automatic Representations for Fundamental Groups of Torus Bundles over the Circle
We construct a new family of Cayley automatic representations of semidirect products \(\mathbb {Z}^n \rtimes _A \mathbb {Z}\) for which none of the projections of the normal subgroup \(\mathbb {Z}^n\) onto each of its cyclic components is finite automaton recognizable. For \(n=2\) we describe a family of matrices from \(\mathrm {GL}(2,\mathbb {Z})\) corresponding to these representations. We are motivated by a problem of characterization of all possible Cayley automatic representations of these groups.- 25 February 2020
- Published by Springer Nature
- Vol. 12038, 115-127
Open AccessNonstandard Cayley Automatic Representations for Fundamental Groups of Torus Bundles over the Circle
We construct a new family of Cayley automatic representations of semidirect products \(\mathbb {Z}^n \rtimes _A \mathbb {Z}\) for which none of the projections of the normal subgroup \(\mathbb {Z}^n\) onto each of its cyclic components is finite automaton recognizable. For \(n=2\) we describe a family of matrices from \(\mathrm {GL}(2,\mathbb {Z})\) corresponding to these representations. We are motivated by a problem of characterization of all possible Cayley automatic representations of these groups.