A4 Refereed article in a conference publication
Reachability in Linear Recurrence Automata
Authors: Hirvensalo, Mika; Kawamura, Akitoshi; Potapov, Igor; Yuyama, Takao
Editors: Kovács, Laura; Sokolova, Ana
Conference name: International Conference on Reachability Problems
Publisher: Springer Nature Switzerland
Publication year: 2024
Journal: Lecture Notes in Computer Science
Book title : Reachability Problems : 18th International Conference, RP 2024, Vienna, Austria, September 25–27, 2024, Proceedings
Issue: 15050
First page : 167
Last page: 183
ISBN: 978-3-031-72620-0
eISBN: 978-3-031-72621-7
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-72621-7_12
Web address : http://doi.org/10.1007/978-3-031-72621-7_12
This paper studies the linear recurrence automata model in which multiple linear recurrences can be used to generate sequences of numbers. We parameterised the model by varying several structural properties to identify under which constraints or extensions the reachability problems become computationally hard and undecidable. We show first the reduction of classical matrix semigroup problems to reachability in linear recurrence automata and then analyse several variants of the model restricting the state structures, the number and the depth of recurrences.
