BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1022
DTSTAMP:20230914T125947Z
SUMMARY:Affine Subspace Reachability Problem
DESCRIPTION:Speaker: Prabhat Kumar Jha\n\nAbstract: \nAbstract: Discrete-
time linear systems are a ubiquitous modeling tool across the sciences. We
study a reachability problem related to discrete-time linear systems whic
h we call ``Affine Subspace Reachability Problem''. Given a linear operato
r $M$\, a vector $v$ and an affine subspace $W$\, this problem asks whethe
r there is a time $t$ such that $M^tv$ is in $W$. A rich body of researc
h has developed around several special cases of this problem\, such as the
Orbit Problem\, the Skolem Problem and the Extended Orbit Problem.\n\\par
In this report\, we survey some of the results known about the various sp
ecial cases of the Affine Subspace Reachability Problem. We begin by obser
ving the equivalence of the ``Affine Subspace Reachability Problem'' with
some special cases as an immediate consequence of famous Skolem-Mahler-Lec
h theorem. We then provide a constructive proof of Skolem-Mahler-Lech theo
rem for the case when the eigenvalues of $M$ are roots of real numbers. We
use this proof to construct an algorithm for the Skolem Problem for the s
ame case.\n\\par We then investigate the limitation of our proof technique
by exhibiting a decidable problem for which the eigenvalues of the corres
ponding $M$ are not roots of real numbers. More specifically\, we consider
the sequence $a_t = \\cos t \\theta$ (where $\\theta$ is not a rational m
ultiple of $\\pi$ and $\\cos \\theta$ is algebraic)\, and show that the pr
oblem of whether there exists a $t$ such that $a_t = c$ is a decidable spe
cial case of the general affine subspace reachability problem. We also exh
ibit that the eigenvalues of the corresponding matrix are not roots of rea
ls.\n\\par We also show efficient decidability of the problem of decidin
g if a state of an ergodic Markov chain can approximately achieve a given
probability starting from the distribution in which the system is in a giv
en state with probability 1.\n\\par This work is done to prepare a ground
for future works in the direction of verification of succinctly represente
d probabilistic models such as the Ising model.\n(This is done under the s
upervision of S Akshay (IIT B) and Piyush Srivastava)\n
URL:https://www.tcs.tifr.res.in/web/events/1022
DTSTART;TZID=Asia/Kolkata:20191205T153000
DTEND;TZID=Asia/Kolkata:20191205T163000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR