Orbits of linear maps and regular languages
Tóm tắt
The equivalence is established of the problem of hitting a polyhedral set by the orbit of a linear map and the intersection of a regular language and a language of permutations of binary words (
$$P_\mathbb{B}$$
-realizability problem). The decidability of the both problems is presently unknown, and the first one is a straightforward generalization of the famous Skolem problem and the nonnegativity problem in the theory of linear recurrent sequences.
Tài liệu tham khảo
J. Berstel and Ch. Reutenauer, Rational Series and Their Languages (Springer, New York, 1988).
V. D. Blondel and N. Portier, “The Presence of a Zero in an Integer Linear Recurrent Sequence is NP-Hard to Decide,” Linear Algebra Appl. 351–352, 91–98 (2002).
W. Cook, J. Fonlupt, and A. Schrijver, “An Integer Analogue of Carathéodory’s Theorem,” J. Combin. Theory Ser. B, 40(1), 63–70 (1986).
F. Eisenbrand and G. Shmonin, “Carathéodory Bounds for Integer Cones,” Oper. Res. Lett. 34, 564–568 (2006).
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San-Francisco, 1979; Mir, Moscow, 1982).
V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki, Skolem’s Problem-On the Border between Decidability and Undecidability, TUCS Tech. Rep. No. 683 (2005).
J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, Reading, 2001; Williams, Moscow, 2002).
V. Laohakosol and P. Tangsupphathawat, “Positivity of ThirdOrder Linear Recurrence Sequences,” Discrete Appl.Math. 157(15), 3239–3248 (2009).
A. Salomaa and M. Soittola, Automata-Theoretic Aspects of Formal Power Series (Springer, New York, 1978).
A. Schrijver, Theory of Linear and Integer Programming, Vols. 1, 2 (Wiley & Sons, Chichester, 1986; Mir, Moscow, 1991).
A. Shen and N. K. Vereshchagin, Computable Functions (AMS, Providence, 2003; MTsNMO, Moscow, 2008).
R. P. Stanley, Enumerative Combinatorics, Vol. 1 (Wadsworth & Brooks, Monterey, California, 1986; Mir, Moscow, 1990).
T. Tao, “Open Question: Effective Skolem-Mahler-Lech Theorem,” http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/.
N. K. Vereshchagin, “On Occurrence of Zero in a Linear Recursive Sequence,” Mat. Zametki 38(2), 177–189 (1985) [Math. Notes 38, 609–615 (1985)].