@inproceedings{KannanLipton:STOC:1980,
    Abstract = {The ``accessibility problem'' for linear sequential machines (Harrison [7]) is the problem of deciding whether there is an input x that sends such a machine from a given state q1 to a given state q2. Harrison [7] showed that this problem is reducible to the ``orbit problem:'' Given AεQn\texttimes{}n does there exist iεN such that Aix =y.* We will call this the ``orbit problem'' because the question can be rephrased as: Does y belong to the orbit of x under A where the ``orbit of x under A'' is the set {Aix: i = 0,1,2,...}. (A0 is the identity matrix I.) In Harrison's original problem the elements of A,x, and y were members of an arbitrary ``computable'' field. In view of the lack of structure of such fields, we study only the rationals. Shank [13] proves that the orbit problem is decidable for the rational case when n=2. The current paper establishes that for the general rational case, the problem is decidable - and in fact polynomial-time decidable.We wish to give a brief idea of our approach to the problem.},
    Address = {New York, NY, USA},
    Author = {Kannan, Ravindran and Lipton, Richard J.},
    BookTitle = {Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing},
    File = {The orbit problem is decidable - 800141.804673 - n - n.pdf},
    ISBN = {0897910176},
    Location = {Los Angeles, California, USA},
    Pages = {252--261},
    Publisher = {Association for Computing Machinery},
    Series = {STOC '80},
    Title = {The Orbit Problem is Decidable},
    URL = {https://doi.org/10.1145/800141.804673},
    Year = {1980},
    bdsk-url-1 = {https://doi.org/10.1145/800141.804673},
    date-added = {2021-03-03 12:09:39 +0100},
    date-modified = {2023-08-22 15:40:30 +0200},
    numpages = {10},
    doi = {10.1145/800141.804673}
}

@inproceedings{KannanLipton:STOC:1980, Abstract = {The accessibility problem'' for linear sequential machines (Harrison [7]) is the problem of deciding whether there is an input x that sends such a machine from a given state q1 to a given state q2. Harrison [7] showed that this problem is reducible to theorbit problem:'' Given AεQn\texttimes{}n does there exist iεN such that Aix =y.* We will call this the orbit problem'' because the question can be rephrased as: Does y belong to the orbit of x under A where theorbit of x under A'' is the set {Aix: i = 0,1,2,...}. (A0 is the identity matrix I.) In Harrison's original problem the elements of A,x, and y were members of an arbitrary ``computable'' field. In view of the lack of structure of such fields, we study only the rationals. Shank [13] proves that the orbit problem is decidable for the rational case when n=2. The current paper establishes that for the general rational case, the problem is decidable - and in fact polynomial-time decidable.We wish to give a brief idea of our approach to the problem.}, Address = {New York, NY, USA}, Author = {Kannan, Ravindran and Lipton, Richard J.}, BookTitle = {Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing}, File = {The orbit problem is decidable - 800141.804673 - n - n.pdf}, ISBN = {0897910176}, Location = {Los Angeles, California, USA}, Pages = {252--261}, Publisher = {Association for Computing Machinery}, Series = {STOC '80}, Title = {The Orbit Problem is Decidable}, URL = {https://doi.org/10.1145/800141.804673}, Year = {1980}, bdsk-url-1 = {https://doi.org/10.1145/800141.804673}, date-added = {2021-03-03 12:09:39 +0100}, date-modified = {2023-08-22 15:40:30 +0200}, numpages = {10}, doi = {10.1145/800141.804673} }