Orbits of Linear Maps and Regular Languages

DOI10.1007/978-3-642-20712-9_24zbMATH Open1332.68130arXiv1011.1842OpenAlexW1996102424MaRDI QIDQ3007635FDOQ3007635

Mikhail Vyalyi, Sergey P. Tarasov

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1011.1842

zbMATH Keywords

regular languagedecidabilitylinear recurrence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Cites Work

• On Context-Free Languages
• On Models of a Nondeterministic Computation
• Occurrence of zero in a linear recursive sequence
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
• Orbits of Linear Maps and Regular Languages
• Title not available (Why is that?)
• Lowering Undecidability Bounds for Decision Questions in Matrices

Cited In (7)

• Points d'orbite dense de certains langages de mots infinis
• Algebraic model checking for discrete linear dynamical systems
• Finite Orbits of Language Operations
• Orbits of Linear Maps and Regular Languages
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• From decidability to undecidability by considering regular sets of instances
• What's decidable about discrete linear dynamical systems?

This page was built for publication: Orbits of Linear Maps and Regular Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007635)