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