A1 Refereed original research article in a scientific journal
Decision Problems on Unary Probabilistic and Quantum Automata
Authors: Mika Hirvensalo, Abuzer Yakaryilmaz
Publisher: University of Latvia
Publication year: 2016
Journal: Baltic Journal of Modern Computing
Journal acronym: BJMC
Volume: 4
Issue: 4
First page : 965
Last page: 976
Number of pages: 12
ISSN: 2255-8942
eISSN: 2255-8950
DOI: https://doi.org/10.22364/bjmc.2016.4.4.22(external)
It is well known that the emptiness problem for binary probabilistic automata and so
for quantum automata is undecidable. We present the current status of the emptiness problems
for unary probabilistic and quantum automata with connections with Skolem’s and positivity
problems. We also introduce the concept of linear recurrence automata in order to show the
connection naturally. Then, we also give possible generalizations of linear recurrence relations
and automata on vectors