Volume 17, No 6, 2010, P. 2049
UDC 510.53
M. N. Vyalyi, S. P. Tarasov
Orbits of linear maps and regular languages properties
Abstract:
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 wellknown Skolem and nonnegativity problems that are formulated in terms of linear recurrence sequences.
Bibliogr. 14.
Keywords: linear recurrence sequence, linear map, orbit, regular language, algorithmic decidability.
Vialyi Mikhail Nikolaevich ^{1}
Tarasov Sergey Pavlovich ^{1}
1. Computational Center of RAS,
40 Vavilov str., 119333 Moscow, Russia
email: vyalyi@gmail.com, serge99meister@gmail.com
