Orbits of linear maps and regular languages

Details Orbits of linear maps and regular languages Orbits of linear maps and regular languages

2010-11-08

arxiv.org/abs/1011.1842v2

Vyalyi M., Tarasov S. Orbits of linear maps and regular languages. Discrete analysis and operations research. 2010. Vol. 17, N

Computer Science

Formal Languages and Automata Theory

The text combines a journal publication and new results submitted to CSR 2011. 33 pages, 7 figures

Scientific paper

We settle the equivalence between 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 (the permutation filter 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. To show a `borderline' status of the permutation filter realizability problem with respect to computability we present some decidable and undecidable problems closely related to it.

Affiliated with

Also associated with

No associations

Rating

Orbits of linear maps and regular languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Orbits of linear maps and regular languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Orbits of linear maps and regular languages will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-131658