Volume 17, No 6, 2010, P. 20-49
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 well-known 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
e-mail: vyalyi@gmail.com, serge99meister@gmail.com
