On the Complexity of the Orbit Problem
Tóm tắt
We consider higher-dimensional versions of Kannan and Lipton’s Orbit Problem—determining whether a target vector space ν may be reached from a starting point
Từ khóa
Tài liệu tham khảo
Alan Baker . 1975. Transcendental Number Theory . Cambridge University Press , Cambridge . Alan Baker. 1975. Transcendental Number Theory. Cambridge University Press, Cambridge.
A. Baker and G. Wüstholz . 1993 . Logarithmic forms and group varieties . J. Reine Angew. Math. 442 (1993), 19 -- 62 . A. Baker and G. Wüstholz. 1993. Logarithmic forms and group varieties. J. Reine Angew. Math. 442 (1993), 19--62.
P. Blanksby and H. Montgomery. 1971. Algebraic integers near the unit circle. Acta Arith. (1971) 355--369. P. Blanksby and H. Montgomery. 1971. Algebraic integers near the unit circle. Acta Arith. (1971) 355--369.
H. Cohen . 1993. A Course in Computational Algebraic Number Theory . Springer , Berlin . H. Cohen. 1993. A Course in Computational Algebraic Number Theory. Springer, Berlin.
Graham Everest Alf van der Poorten Thomas Ward and Igor Shparlinski. 2003. Recurrence Sequences. American Mathematical Society Washington DC. Graham Everest Alf van der Poorten Thomas Ward and Igor Shparlinski. 2003. Recurrence Sequences. American Mathematical Society Washington DC.
V. Halava , T. Harju , M. Hirvensalo , and J. Karhumäki . 2005 . Skolem’s Problem -- On the Border between Decidability and Undecidability . Technical Report 683. Turku Centre for Computer Science. V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki. 2005. Skolem’s Problem -- On the Border between Decidability and Undecidability. Technical Report 683. Turku Centre for Computer Science.
Michael A. Harrison . 1969. Lectures on Linear Sequential Machines . Academic Press , New York, NY . Michael A. Harrison. 1969. Lectures on Linear Sequential Machines. Academic Press, New York, NY.
L. Kronecker . 1875 . Zwei sätze über gleichungen mit ganzzahligen koeffizienten . J. Reine Angew. Math. 53 (1875), 173 -- 175 . L. Kronecker. 1875. Zwei sätze über gleichungen mit ganzzahligen koeffizienten. J. Reine Angew. Math. 53 (1875), 173--175.
Christer Lech . 1953. A note on recurring series. Arkiv för Matematik 2 ( 1953 ), 417--421. Christer Lech. 1953. A note on recurring series. Arkiv för Matematik 2 (1953), 417--421.
B. Litow . 1997 . A decision method for the rational sequence problem . In Electronic Colloquium on Computational Complexity (ECCC) , Vol. 4 . B. Litow. 1997. A decision method for the rational sequence problem. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 4.
K. Mahler . 1935 . Eine arithmetische eigenschaft der Taylor-koeffizienten rationaler funktionen . Proc. Akad. Wet. Amsterdam 38 (1935), 51 -- 60 . K. Mahler. 1935. Eine arithmetische eigenschaft der Taylor-koeffizienten rationaler funktionen. Proc. Akad. Wet. Amsterdam 38 (1935), 51--60.
M. Mignotte. 1982. Some useful bounds. Comput. Algebr. (1982) 259--263. M. Mignotte. 1982. Some useful bounds. Comput. Algebr. (1982) 259--263.
M. Mignotte , T. Shorey , and R. Tijdeman . 1984 . The distance between terms of an algebraic recurrence sequence . Jour. Reine Angew. Math. 349 (1984), 63 -- 76 . M. Mignotte, T. Shorey, and R. Tijdeman. 1984. The distance between terms of an algebraic recurrence sequence. Jour. Reine Angew. Math. 349 (1984), 63--76.
Arto Salomaa and Matti Soittola . 1978. Automata—Theoretic Aspects of Formal Power Series . Springer-Verlag , Berlin . Arto Salomaa and Matti Soittola. 1978. Automata—Theoretic Aspects of Formal Power Series. Springer-Verlag, Berlin.
Arnold Schönhage . 1979. On the power of random access machines . In Automata, Languages and Programming, Hermann Maurer (Ed.). Lecture Notes in Computer Science , Vol. 71 . Springer , Berlin , 520--529. Arnold Schönhage. 1979. On the power of random access machines. In Automata, Languages and Programming, Hermann Maurer (Ed.). Lecture Notes in Computer Science, Vol. 71. Springer, Berlin, 520--529.
Th. Skolem . 1934 . Ein verfahren zur behandlung gewisser exponentialer gleichungen und diophantischer gleichungen . Skand. Mat. Kongr. 8 (1934), 163 -- 188 . Th. Skolem. 1934. Ein verfahren zur behandlung gewisser exponentialer gleichungen und diophantischer gleichungen. Skand. Mat. Kongr. 8 (1934), 163--188.
I. Stewart and D. Tall. 2002. Algebraic Number Theory and Fermat’s Last Theorem (3rd ed.). A. K. Peters. I. Stewart and D. Tall. 2002. Algebraic Number Theory and Fermat’s Last Theorem (3rd ed.). A. K. Peters.
T. Tao . 2008. Structure and Randomness: Pages from Year One of a Mathematical Blog . American Mathematical Society, Washington, DC. T. Tao. 2008. Structure and Randomness: Pages from Year One of a Mathematical Blog. American Mathematical Society, Washington, DC.
Sergey Tarasov and Mikhail Vyalyi . 2011. Orbits of linear maps and regular languages . In Computer Science -- Theory and Applications, Alexander Kulikov and Nikolay Vereshchagin (Eds.) . Lecture Notes in Computer Science , Vol. 6651 . Springer , Berlin , 305--316. DOI:http://dx.doi.org/10.1007/978-3-642-20712-9_24 10.1007/978-3-642-20712-9_24 Sergey Tarasov and Mikhail Vyalyi. 2011. Orbits of linear maps and regular languages. In Computer Science -- Theory and Applications, Alexander Kulikov and Nikolay Vereshchagin (Eds.). Lecture Notes in Computer Science, Vol. 6651. Springer, Berlin, 305--316. DOI:http://dx.doi.org/10.1007/978-3-642-20712-9_24
Ashish Tiwari . 2004. Termination of linear programs . In Computer Aided Verification . Springer , Berlin , 70--82. Ashish Tiwari. 2004. Termination of linear programs. In Computer Aided Verification. Springer, Berlin, 70--82.
Alfred Jacobus van der Poorten. 1977. Linear forms in logarithms in the p-adic case. Transcend. Theor. Adv. Appl. (1977) 29--57. Alfred Jacobus van der Poorten. 1977. Linear forms in logarithms in the p-adic case. Transcend. Theor. Adv. Appl. (1977) 29--57.