Enric Ventura (2014)

# Orbit Decidability, Applications and Variations

In: Extended Abstracts Fall 2012, ed. by González-Meneses, Juan and Lustig, Martin and Ventura, Enric, pp. 91–95, Springer International Publishing. Trends in Mathematics. (ISBN: 978-3-319-05487-2, 978-3-319-05488-9).

Orbit DecidabilityIn many areas of mathematics and in innumerable topics and situations, the notion of transformation plays an important role. If X is the set or collection of objects we are interested in, a transformation of X is usually understood to be just a map TeXalpha: X rightarrow X . And whenever the context highlights a certain collection of “interesting” maps A ⊆ Map(X, X) (namely, endomorphisms or automorphisms of X if X is an algebraic structure, continuous maps or isometries of X if X is a topological or a geometric object, etc.), one naturally has the notion of orbit: the A-orbit of a point x ∈ X is the set of all its A-images xA = \ xα∣α ∈ A\ ⊆ X. In all these situations, there is a problem which is usually crucial when studying algorithmic aspects of many of the interesting problems one can formulate about the objects in X and how do they relate to each other under the transformations in A, namely orbit decidability.Definition 1.Let X be a set, and let A ⊆ Map(X, X

Document Actions