Geodesic
Orbits of linear maps and regular languages properties
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 20-49.

Voir la notice de l'article provenant de la source Math-Net.Ru

We establish equivalence of two recognition problems: hitting of a polyhedral set by an orbit of a linear map and nonemptiness of the intersection of a regular language and the language of binary words permutations (the permutation filter). Decidability is unknown for both problems. The hitting problem generalizes well-known Skolem and nonnegativity problems that are formulated in terms of linear recurrence sequences. Bibliogr. 14.
Keywords: linear recurrence sequence, linear map, regular language, algorithmic decidability.
Mots-clés : orbit 
@article{DA_2010_17_6_a1,
     author = {M. N. Vyalyi and S. P. Tarasov},
     title = {Orbits of linear maps and regular languages properties},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {20--49},
     publisher = {mathdoc},
     volume = {17},
     number = {6},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_6_a1/}
}
TY  - JOUR
AU  - M. N. Vyalyi
AU  - S. P. Tarasov
TI  - Orbits of linear maps and regular languages properties
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 20
EP  - 49
VL  - 17
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_6_a1/
LA  - ru
ID  - DA_2010_17_6_a1
ER  - 
%0 Journal Article
%A M. N. Vyalyi
%A S. P. Tarasov
%T Orbits of linear maps and regular languages properties
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 20-49
%V 17
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_6_a1/
%G ru
%F DA_2010_17_6_a1
M. N. Vyalyi; S. P. Tarasov. Orbits of linear maps and regular languages properties. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 20-49. http://geodesic.mathdoc.fr/item/DA_2010_17_6_a1/

[1] Vereschagin N. K., “O probleme poyavleniya nulya v lineinoi rekurrentnoi posledovatelnosti”, Mat. zametki, 38:2 (1985), 177–189 | MR | Zbl

[2] Vereschagin N. V., Shen A., Lektsii po matematicheskoi logike i teorii algoritmov{. Chast 3.} Vychislimye funktsii, MTsNMO, M., 2008, 192 pp.

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[4] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, v. 1, Mir, M., 1991, 360 pp. ; т. 2, 342 с. | MR

[5] Stenli R., Perechislitelnaya kombinatorika, Mir, M., 1990, 440 pp. | MR

[6] Khopkroft D., Motvani R., Ulman D., Vvedenie v teoriyu avtomatov, yazykov i vychislenii, Vilyams, M., 2002, 528 pp.

[7] Berstel J., Reutenauer Ch., Rational series and their languages, Springer-Verl., New York–Heidelberg–Berlin, 1988, 151 pp. | MR | Zbl

[8] Blondel V. D., Portier N., “The presence of a zero in an integer linear recurrent sequence is NP-hard to decide”, Linear Algebra Appl., 351–352 (2002), 91–98 | DOI | MR | Zbl

[9] Cook W., Fonlupt J., Schrijver A., “An integer analogue of Carathéodory's theorem”, J. Comb. Theory. Ser. B, 40:1 (1986), 63–70 | DOI | MR | Zbl

[10] Eisenbrand F., Shmonin G., “Carathéodory bounds for integer cones”, Oper. Res. Lett., 34 (2006), 564–568 | DOI | MR | Zbl

[11] Halava V., Harju T., Hirvensalo M., Karhumäki J., Skolem's problem – on the border between decidability and undecidability, TUCS Tech. Rep. No 683, 2005, 42 pp.

[12] Laohakosol V., Tangsupphathawat P., “Positivity of third order linear recurrence sequences”, Discrete Appl. Math., 157:15 (2009), 3239–3248 | DOI | MR | Zbl

[13] Salomaa A., Soittola M., Automata-theoretic aspects of formal power series, Springer-Verl., New York–Heidelberg–Berlin, 1978, 176 pp. | MR | Zbl

[14] Tao T., Open question: effective Skolem–Mahler–Lech theorem http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/