Orbits of linear maps and regular languages

DOI10.1007/978-3-642-20712-9_24MaRDI QIDQ3007635zbMATH OpenOpenAlexFDO

Authors Sergey P. Tarasov, Mikhail Vyalyi

Publication date 17 June 2011

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

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)

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.

Recommendations

• Orbits of linear maps and properties of regular languages
• On regular realizability problems
• Polynomial-time algorithm for the orbit problem
• On the complexity of the orbit problem
• The polyhedron-hitting problem

Cites work

• Lowering Undecidability Bounds for Decision Questions in Matrices
• Occurrence of zero in a linear recursive sequence
• On Context-Free Languages
• On Models of a Nondeterministic Computation
• Orbits of linear maps and properties of regular languages
• Orbits of linear maps and regular languages
• The presence of a zero in an integer linear recurrent sequence is NP-hard to decide

Cited in

(8)

• Points d'orbite dense de certains langages de mots infinis
• Algebraic model checking for discrete linear dynamical systems
• Orbits of linear maps and regular languages
• Orbits of linear maps and properties of regular languages
• Finite Orbits of Language Operations
• 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)