Orbits of Linear Maps and Regular Languages

DOI10.1007/978-3-642-20712-9_24zbMath1332.68130arXiv1011.1842OpenAlexW1996102424MaRDI QIDQ3007635

Mikhail N. Vyalyi, Sergey P. Tarasov

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

decidabilitylinear recurrenceregular language

Mathematics Subject Classification ID

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

Related Items (5)

What's decidable about discrete linear dynamical systems? ⋮ 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 ⋮ Algebraic model checking for discrete linear dynamical systems

Cites Work

• 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
• On Models of a Nondeterministic Computation
• Lowering Undecidability Bounds for Decision Questions in Matrices
• On Context-Free Languages
• Unnamed Item

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