@article{10.1145/6490.6496,
    Abstract = {The accessibility problem for linear sequential machines [12] is the problem of deciding whether there is an input x such that on x the machine starting in a given state q1 goes to a given state q2. Harrison shows that this problem is reducible to the following simply stated linear algebra problem, which we call the "orbit problem":Given (n, A, x, y), where n is a natural number and A, x, and y are nxn, nx1, and nx1 matrices of rationals, respectively, decide whether there is a natural number I such that Aix=y.He conjectured that the orbit problem is decidable. No progress was made on the conjecture for ten years until Shank [22] showed that if n is fixed at 2, then the problem is decidable. This paper shows that the orbit problem for general n is decidable and indeed decidable in polynomial time. The orbit problem arises in several contexts; two of these, linear recurrences and the discrete logarithm problem for polynomials, are discussed, and we apply our algorithm for the orbit problem in these contexts.},
    Address = {New York, NY, USA},
    Author = {Kannan, R. and Lipton, R. J.},
    File = {Polynomial-Time Algorithm for the Orbit Problem - 6490.6496 - e - e.pdf},
    ISSN = {0004-5411},
    Journal = {J. ACM},
    Month = {August},
    Number = {4},
    Pages = {808--821},
    Publisher = {Association for Computing Machinery},
    Title = {Polynomial-Time Algorithm for the Orbit Problem},
    URL = {https://doi.org/10.1145/6490.6496},
    Volume = {33},
    Year = {1986},
    bdsk-url-1 = {https://doi.org/10.1145/6490.6496},
    date-added = {2021-03-03 12:14:18 +0100},
    date-modified = {2021-03-03 12:14:18 +0100},
    issue_date = {Oct. 1986},
    numpages = {14},
    doi = {10.1145/6490.6496}
}

@article{10.1145/6490.6496, Abstract = {The accessibility problem for linear sequential machines [12] is the problem of deciding whether there is an input x such that on x the machine starting in a given state q1 goes to a given state q2. Harrison shows that this problem is reducible to the following simply stated linear algebra problem, which we call the "orbit problem":Given (n, A, x, y), where n is a natural number and A, x, and y are nxn, nx1, and nx1 matrices of rationals, respectively, decide whether there is a natural number I such that Aix=y.He conjectured that the orbit problem is decidable. No progress was made on the conjecture for ten years until Shank [22] showed that if n is fixed at 2, then the problem is decidable. This paper shows that the orbit problem for general n is decidable and indeed decidable in polynomial time. The orbit problem arises in several contexts; two of these, linear recurrences and the discrete logarithm problem for polynomials, are discussed, and we apply our algorithm for the orbit problem in these contexts.}, Address = {New York, NY, USA}, Author = {Kannan, R. and Lipton, R. J.}, File = {Polynomial-Time Algorithm for the Orbit Problem - 6490.6496 - e - e.pdf}, ISSN = {0004-5411}, Journal = {J. ACM}, Month = {August}, Number = {4}, Pages = {808--821}, Publisher = {Association for Computing Machinery}, Title = {Polynomial-Time Algorithm for the Orbit Problem}, URL = {https://doi.org/10.1145/6490.6496}, Volume = {33}, Year = {1986}, bdsk-url-1 = {https://doi.org/10.1145/6490.6496}, date-added = {2021-03-03 12:14:18 +0100}, date-modified = {2021-03-03 12:14:18 +0100}, issue_date = {Oct. 1986}, numpages = {14}, doi = {10.1145/6490.6496} }