17 research outputs found
Cayley Linear-Time Computable Groups
No full textThis paper looks at the class of groups admitting normal forms for which theright multiplication by a group element is computed in linear time on amulti-tape Turing machine. We show that the groups , and Thompson's group havenormal forms for which the right multiplication by a group element is computedin linear time on a -tape Turing machine. This refines the resultspreviously established by Elder and the authors that these groups are Cayleypolynomial-time computable.Comment: Published in journal of Groups, Complexity, Cryptolog
BEING CAYLEY AUTOMATIC IS CLOSED UNDER TAKING WREATH PRODUCT WITH VIRTUALLY CYCLIC GROUPS
No full textAbstract
We extend work of Berdinsky and Khoussainov [‘Cayley automatic representations of wreath products’, International Journal of Foundations of Computer Science27(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.</jats:p
Cayley Automatic Groups and Numerical Characteristics of Turing Transducers
No full textThis paper is devoted to the problem of finding characterizations for Cayley automatic groups. The concept of Cayley automatic groups was recently introduced by Kharlampovich, Khoussainov and Miasnikov. We address this problem by introducing three numerical characteristics of Turing transducers: growth functions, Folner functions and average length growth functions. These three numerical characteristics are the analogs of growth functions, Folner functions and drifts of simple random walks for Cayley graphs of groups. We study these numerical characteristics for Turing transducers obtained from automatic presentations of labeled directed graphs.12 pages; minor updates; some references adde
Nonstandard Cayley Automatic Representations for Fundamental Groups of Torus Bundles over the Circle
No full textCayley Linear-Time Computable Groups
No full textThis paper looks at the class of groups admitting normal forms for which the
right multiplication by a group element is computed in linear time on a
multi-tape Turing machine. We show that the groups , and Thompson's group have
normal forms for which the right multiplication by a group element is computed
in linear time on a -tape Turing machine. This refines the results
previously established by Elder and the authors that these groups are Cayley
polynomial-time computable.Comment: Published in journal of Groups, Complexity, Cryptolog
Finite Automata Encoding Piecewise Polynomials
No full textFinite 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 in as a convolution of its coordinates written in some base. Then a figure is said to be encoded as a finite automaton if the set of convolutions corresponding to the points in this figure is accepted by a finite automaton. The only 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. Such representation naturally comes from the framework of hierarchical tensor product B-splines, which are piecewise polynomials widely utilized in numerical computational geometry. We show that finite automata provide a suitable tool for solving computational problems arising in this framework when the support of a function is unbounded.25 pages; we updated the introduction and added new reference
Extending the Synchronous Fellow Traveler Property
No full textWe 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 non-existence theorems.18 pages, 6 figures; accepted versio
