A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Reachability in Linear Recurrence Automata
Tekijät: Hirvensalo, Mika; Kawamura, Akitoshi; Potapov, Igor; Yuyama, Takao
Toimittaja: Kovács, Laura; Sokolova, Ana
Konferenssin vakiintunut nimi: International Conference on Reachability Problems
Kustantaja: Springer Nature Switzerland
Julkaisuvuosi: 2024
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Reachability Problems : 18th International Conference, RP 2024, Vienna, Austria, September 25–27, 2024, Proceedings
Numero: 15050
Aloitussivu: 167
Lopetussivu: 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
Verkko-osoite: 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.
